cyk追楠神系列三

绝地灬酷狼 2022-11-22 00:05 113阅读 0赞

## cyk追楠神系列三 ##

Description  
众所周知，cyk给楠神写了一封信表白。作为有一个有礼貌的五好青年，楠神当然得给 cyk 写一封回信咯，俗称“好人信”。

楠神是一个非常有文采的人，他在信里引用了很多名言来安慰 cyk，有时候他觉得一句话很好的话，他会引用很多次。现在他想考考 cyk，在告诉 cyk 里面每句名言的情况下，看看 cyk 能不能找到每局名言在信里被引用了多少次。如果能找到的话，说明 cyk 也是一个有涵养的人，楠神对 cyk 的好感度就会增加。

cyk 语文和眼力那么差，当然不行咯，所以你赶快帮帮 cyk 吧！

Input  
输入数据有多组（数据组数不超过 50），到 EOF 结束。

每组数据第一行输入一串字符串，代表楠神写的回信，长度不超过 10^6。

第二行输出 n (1 <= n <= 100)，接下来 n 行每行一个字符串，代表楠神引用的名言，长度不超过 10^6。

Output  
每组数据中，对于每句名言输出他被引用的次数，每个答案占一行。

Sample  
Input  
In fact, maybe we can become good friend, but don’t lose hear for yourselves, when there is a will, there is a way, you can become a better man~  
1  
when there is a will, there is a way  
Output  
1  
Hint  
子串在主串中的匹配允许重叠。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int next[1000005];
    void get_next(char s2[])
    {
        
        int i=0,j=-1;
        int len2=strlen(s2);
        next[0]=-1;
        while(i<len2)
        {
        
            if(j==-1||s2[i]==s2[j])
            {
        
                i++;j++;
                next[i]=j;
            }
            else
            {
        
                j=next[j];
            }
        }
    }
    void kmp(char s1[],char s2[])
    {
        
        int i=0,j=0,cn=0;
        int len1=strlen(s1),len2=strlen(s2);
        get_next(s2);
        while(i<=len1&&j<=len2)
        {
        
            if(j==-1||s1[i]==s2[j])
            {
        
                i++;j++;
            }
            else
            {
        
                j=next[j];
            }
            if(j==len2)
            {
        
              cn++;
              j=0;
            }
        }
        printf("%d\n",cn);
    }
    int main()
    {
        
        char s1[1000001],s2[1000001];
        int n;
        while(gets(s1)!=NULL)
        {
        
            scanf("%d",&n);getchar();
            while(n--)
            {
        
                gets(s2);
                kmp(s1,s2);
            }
        }
        return 0;
    }