----------------------------

一 模板

----------------------------

const int maxn=1111111
char s[maxn];
char p[maxn];
int next[maxn];
void getnext(char *p,int *next){
    int i=0,j=-1;
    int len=strlen(p);
    next[0]=-1;
    while(i<len){
        if(j==-1 || p[i]==p[j]){
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
void kmp(char *s,char *p,int *next){
    int i=0,j=0;
    int n=strlen(s);
    int m=strlen(p);
    getnext(p,next);
    while(i<n){
        if(j==-1 || s[i]==p[j]){
            i++;
            j++;
        }
        else
            j=next[j];
        if(j==m){
            //To DO
            // ans++;
            j=next[j];
        }
    }
}