例题4.7 Oulipo(string从0开始)(大致按照书上默写，但运行超时) 建议重做3次，|||

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

const int MAXW = 10000;
// const int MAXT = 1000000;

string pattern;
string text;

int nexttable[MAXW];

void Getnexttable(int w){
    int i=0;//i是next数组的标号，pattern字符串也是从0开始的，前缀和后缀重合的数量，不用加一
    nexttable[i]=-1;
    int j = nexttable[i];//j是next数组的值，也是跳转到的next编号
    while(i<w){
        if(-1==j||pattern[i]==pattern[j]){
            ++i;
            ++j;
            if(i<w){
                nexttable[i]=j;
            }

        }else{
            j=nexttable[j];
        }
    }
}


int KMPE(int w,int t){

    Getnexttable(w);
    int i=0;
    int j=0;
    int k=0;

    while(j<t){
        if(-1==i||pattern[i]==text[j]){
            ++i;
            ++j;

        }else{
            i=nexttable[i];
        }
        if(i==w){
            ++k;
            j=j-i+2;
            i=0;
        }
    }
    return k;


}


int main(){

    int n;
    scanf("%d",&n);
    for(int i=0;i < n;++i){
        cin>>pattern;
        cin>>text;
        int w = pattern.size();
        int t = text.size();

        printf("%d\n",KMPE(w,t));

    }

}