KMP算法 --数据结构实验之串一：KMP简单应用

你的名字 2022-09-25 01:27 152阅读 0赞

## 数据结构实验之串一：KMP简单应用 ##

####  ####

#### Time Limit: 1000MS Memory limit: 65536K ####

## 题目描述 ##

给定两个字符串string1和string2，判断string2是否为string1的子串。

## 输入 ##

输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。

## 输出 ##

对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。

## 示例输入 ##

abc
    a
    123456
    45
    abc
    ddd

## 示例输出 ##

1
    4
    -1

## 提示 ##

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    char t[1000005],p[1000005];//T为主串，P为模式串
    int next[1000005];
    int lent;
    int lenp;
    //求NEXT函数
    void getnext(char p[])
    {
        int i=0,j=-1;
        next[0]=-1;
        while(i<lenp)
        {
            if(j==-1||p[i]==p[j])
            {
                i++;
                j++;
                if(p[i]!=p[j])
                {next[i]=j;}
                else
                {
                    next[i]=next[j];
                }
            }
            else
            {
                j=next[j];
            }
        }
    }
    //匹配
    void kmp(char t[],char p[])
    {
        int i,j;
        i=j=0;
        while(i<lent&&j<lenp)
        {
            if(j==-1||t[i]==p[j])
            {
                i++;
                j++;
            }
            else
            {
                j=next[j];
            }
        }
        if(j==lenp)
        {
            printf("%d\n",i-lenp+1);
        }
        else
        {
            printf("-1\n");
        }
    }
    
    int main()
    {
        while(~scanf("%s %s",&t,&p))
        {
            lent=strlen(t);
            lenp=strlen(p);
            getnext(p);
            kmp(t,p);
        }
        return 0;
    }