首先第一题

戳我穿越;

题目大意好理解，每组输入一个子串和一个母串，问在母串中有多少个子串？

文明人不要暴力，因为宽度会超时，除去暴力后这就是赤果果的KMP

KMP的重点在于在子串中建立一个匹配表，记录 到每一位的 前缀后缀 中的相同的子子串的最大长度

然后在比较子母串的时候当遇到不同时 后移的位数就是前面相同的个数减去对应的匹配表例的数

额 讲的不清不楚 那推荐戳这里：

那这题就是个裸的KMP模板

code 还是很简单的

#include
     
      #include
      
       using namespace std;char cword[10001];int num[10001];char mword[1000001];int main(){    int t,sum,i,x,j,y;    char temp;    while (~scanf("%d",&t))    {        while (t--)        {            sum=0;            j=-1;i=0;            num[0]=-1;            scanf("%s",cword);            scanf("%s",mword);            x=strlen(cword);            y=strlen(mword);            while (i
      
     

 

第二题 ：

输出一个单词里最多是由多少个子串重复连接而成 注意 是重复 连接 而成，如abefab因为ab没有连接,所以应该输出1

 

也是kmp的应用，考虑有特殊情况

code更短

#include
     
      #include
      
       using namespace std;char yj[1000001];int jjc[1000001];int main(){    int i,j,x,n;    while (~scanf("%s",yj))    {        if (yj[0]=='.')            break;        j=-1;        jjc[0]=-1;        x=strlen(yj);        for (i=0;i
      
     

 

第三题：

就是找出一行名字中在前缀后缀中都存在的字串的长度，升序输出

对num数组匹配表的运用，既然在前缀后缀中都存在，那么其字串的最后一个字母必定和整个串的最后一位相同

然后再利用num数组一直向下滚一边

code

#include
     
      #include
      
       #include
       
        using namespace std;char yj[400001];int num[400001];int jjc[400001];int main(){    int i,j,x,t,k;    while (~scanf("%s",yj))    {        j=-1;i=0;        num[0]=-1;        x=strlen(yj);        while (i
        
         =0;i--)            printf("%d ",jjc[i]);        printf("%d\n",x);    }    return 0;}