KMP模板

void getnext(string s){
    nxt[0] = -1;
    int k = -1;
    for (int q = 1; q < s.size(); q++)
    {
        while (k > -1 && s[k + 1] != s[q])
        {
            k = nxt[k];
        }
        if (s[k + 1] == s[q])
        {
            k++;
        }
        nxt[q] = k;
    }
}

int kmp(string s,string a){
    int ans=0;
    int k=-1;
    for (int i = 0; i < s.size(); i++)
    {
        while (k >-1&& a[k + 1] != s[i])
            k = nxt[k];
        if (a[k + 1] == s[i])
            k = k + 1;
        if(k+1>ans)ans=k+1;
        if(ans==a.size())return ans;
    }
    return ans;
}