数据结构实验之串二：字符串匹配

素颜马尾好姑娘i 2022-07-11 01:58 130阅读 0赞

#### Problem Description ####

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

#### Input ####

输入包含多组数据，每组测试数据包含两行，第一行代表string1，第二行代表string2，string1和string2中保证不出现空格。(string1和string2大小不超过100字符)

#### Output ####

对于每组输入数据，若string2是string1的子串，则输出"YES"，否则输出"NO"。

#### Example Input ####

abc
    a
    123456
    45
    abc
    ddd

#### Example Output ####

YES
    YES
    NO

#include<stdio.h>
    char s[106], t[106];
    int  next[101];
    int len1, len2;
    void getnext ()
    {
        int j,k;
        j=0;k=-1;
        next[j]=k;
        while(j<len2)
        {
            if(k==-1||t[j]==t[k])
            {
                next[++j]=++k;
            }
            else
            {
                k=next[k];
            }
        }
    }
    int kmp_count()
    {
        int i,j=0;
        for(i=0;i<len1;i++)
        {
            while(j>0&&s[i]!=t[j])
                j=next[j];
            if(s[i]==t[j])
            {
                j++;
            }
            if(j==len2)
            {
                return 1;
            }
        }
        return 0;
    }
    int main()
    {
        int ans;
        while(scanf("%s %s",s,t)!=EOF)
        {
            len1=strlen(s);
            len2=strlen(t);
            ans=kmp_count();
            if(ans)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
        return 0;
    }