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

灰太狼 2022-07-11 01:58 114阅读 0赞

#### Problem Description ####

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

#### Input ####

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

#### Output ####

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

#### Example Input ####

abc
    a
    123456
    45
    abc
    ddd

#### Example Output ####

1
    4
    -1

#include<stdio.h>
    #include<string.h>
    char str1[1000000], str2[1000000];
    int next[1000001];
    void getnext (int len2)
    {
        int j,k;
        j=0;k=-1;
        next[j]=k;
        while(j<len2)
        {
            if(k==-1||str2[j]==str2[k])
            {
                next[++j]=++k;
            }
            else
            {
                k=next[k];
            }
        }
    } int kmp_count(int len1, int len2)
    {
        int i,j;
        int ans=0;
        j=0;
        getnext(len2);
        for(i=0;i<len1;i++)
        {
            while(j>0&&str2[j]!=str1[i])
            {
                j=next[j];
            }
            if(str1[i]==str2[j])
            {
                j++;
            }
            if(j==len2)
            {
                ans=i-len2+1+1;
                break;
            }
        }
        return ans;
    } 
    int main()
    {
        int len1,len2;
        int ans;
        while(scanf("%s%s",str1,str2)!=EOF)
        {
            memset(next,0,sizeof(next));
            len1=strlen(str1);
            len2=strlen(str2);
            ans=kmp_count(len1,len2);
            if(ans==0)
                printf("-1\n");
            else
                printf("%d\n",ans);
        }
        return 0;
    }