KMP模板

void get_next(string t){
    nex[0] = -1;
    for(int i = 0,k = -1;i < lent;){
        if(k==-1||t[i] == t[k]){
            ++k;++i;
            nex[i]=k;
        }else k = nex[k];
    }
}
bool kmp(string s,string t){
    lens=s.length();
    lent=t.length();
    if(lens<lent)return 0;
    get_next(t);
    int i = 0, j = 0;
    while(i < lens&&j<lent) {
        if(j==-1||s[i] == t[j]){
            i++;j++;
            if(j==lent){
                return 1;
            }
        }else j=nex[j];
    }
    return 0;
}