拓展kmp裸题

自己跟自己匹配即可

模板测试=v=

 

#include 
     
      #include 
      
       using namespace std;const int maxn = 1e6 + 100;char S[maxn];int Next[maxn], extend[maxn];void GetNext(char *T, int *Next){    int len = strlen(T);    Next[0] = len;    int a, p;    for(int i = 1, j = -1; i < len; i++, j--){       if(j < 0 || i + Next[i-a] >= p){            if(j < 0) p = i, j = 0;            while(p < len && T[p] == T[j])                p++, j++;            Next[i] = j;            a = i;       } else Next[i] = Next[i-a];    }}void GetExtend(char *S, char *T, int *extend, int *Next){    GetNext(T, Next);    int a, p;    int slen = strlen(S), tlen = strlen(T);    for(int i = 0, j = -1; i < slen; i++, j--){        if(j < 0 || i + Next[i-a] >= p){            if(j < 0) p = i, j = 0;            while(p < slen && j < tlen && S[p] == T[j]) p++, j++;            extend[i] = j;            a = i;        } else extend[i] = Next[i-a];    }}int main(){       cin>>S;    int len = strlen(S);    GetNext(S, Next);    long long ans = 0;    for(int i = 0; i < len; i++)  ans += Next[i];    cout<
       
        <