找一串字符中完全匹配的起始位置，利用KMP模版：

代码：

1 #include
      
        2 using namespace std; 3 int p[10001]; 4 int a[1000001],b[10001]; 5 int n,m; 6 void getp() 7 { 8     p[1]=0; 9     int i,j=0;10     for(i=2;i<=m;i++)11     {12         while(j>0 && b[j+1]!=b[i]) 13            j=p[j];14         if(b[j+1]==b[i])15            j+=1;16         p[i]=j;17     }18 }19 int kmp()20 {21     int i,j=0;22     for(i=1;i<=n;i++)23     {24         while(j>0 && b[j+1]!=a[i])  25              j=p[j];26         if(b[j+1]==a[i])27              j+=1;28        if(j==m)29        {30           return i-j+1;31           j=p[j];32        }33     }34     return -1;35 }36 37 int main()38 {39     int t;40     int i,j;41     cin>>t;42     while(t--)43     {44         cin>>n>>m;45         for(i=1;i<=n;i++)46           cin>>a[i];47         for(j=1;j<=m;j++)48           cin>>b[j];49         getp();50         cout<
       
        <
       
      

 1686

这个只要在1711的基础上加个标志符，当满足一个完整的匹配时就加1，

代码：

1 #include
      
        2 #include
       
         3 using namespace std; 4 int p[10001]; 5 char a[1000001],b[10001]; 6 int n,m; 7  8 void getp() 9 {10     p[1]=0;11     int i,j=0;12     for(i=2;i<=m;i++)13     {14         while(j>0 && b[j+1]!=b[i]) 15            j=p[j];16         if(b[j+1]==b[i])17            j+=1;18         p[i]=j;19     }20 21 }22 23 24 int kmp()25 {26     int i,j=0,count=0;27     for(i=1;i<=n;i++)28     {29         while(j>0 && b[j+1]!=a[i])  30              j=p[j];31         if(b[j+1]==a[i])32              j+=1;33        if(j==m)34        {35          count++;36           j=p[j];37        }38     }39     return count;40 }41 42 int main()43 {44     int t;45     int i,j;46     cin>>t;47     while(t--)48     {49         cin>>b+1;50         m=strlen(b+1);51         cin>>a+1;52         n=strlen(a+1);53         getp();54         cout<
        
         <
        
       
      

 2203   亲和串

这个关键是要把第一个字符串后面再加个本身的字符串（即看成移位后的结果）用strcat()函数，其他的就和1686一样。

代码：

1 #include
      
        2 #include
       
         3 using namespace std; 4 int p[100001]; 5 char a[200002]; 6 char b[100001]; 7 int n,m; 8 void getp() 9 {10     p[1]=0;11     int i,j=0;12     for(i=2;i<=m;i++)13     {14         while(j>0&& b[j+1]!=b[i])15             j=p[j];16         if(b[j+1]==b[i])17              j+=1;18         p[i]=j;19     }20 }21 22 int kmp()23 {24     int i,j=0;25     for(i=1;i<=n;i++)26     {27         while(j>0&&b[j+1]!=a[i])28             j=p[j];29         if(b[j+1]==a[i])30             j+=1;31         if(j==m)32           return 1;33     }34     return 0;35 }36 37 int main()38 {39     char tmp[100001];40     while(cin>>a+1)41     {42         getchar();43         cin>>b+1;44         m=strlen(b+1);45         strcpy(tmp+1,a+1);46         strcat(a+1,tmp+1);47         n=strlen(a+1);48         getp();49         if(kmp())50           cout<<"yes"<