长文章：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

板题：求子串在主串中出现的次数

#include
      
       using namespace std;const int M=1e6+6;char S[M],T[M];int nextt[M];int ans=0;void makeNext(){    int m=strlen(T);    nextt[0]=0;    for (int i=1,j=0;i
       
        0&&T[i]!=T[j])            j=nextt[j-1];        if(T[i]==T[j])           j++;        nextt[i]=j;    }}void kmp(){    int n,m;    n = strlen(S);    m = strlen(T);    makeNext();    for (int i=0,q=0;i
        
         0&&T[q]!=S[i])            q=nextt[q-1];        if(T[q]==S[i])            q++;        if(q==m)           ans++;    }}  int main() {     while(~scanf("%s%s",S,T))     {         ans=0;        kmp();        printf("%d\n",ans);    }    return 0;}