51nod 1304 字符串的相似度（exkmp）

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e6 + ;
char S[maxn];
int Next[maxn], extend[maxn];
void GetNext(char *T, int *Next){
int len = strlen(T);
Next[] = len;
int a, p;
for(int i = , j = -; i < len; i++, j--){
if(j < || i + Next[i-a] >= p){
if(j < ) p = i, j = ;
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 = , j = -; i < slen; i++, j--){
if(j < || i + Next[i-a] >= p){
if(j < ) p = i, j = ;
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 = ;
for(int i = ; i < len; i++) ans += Next[i];
cout<<ans<<endl;
return ;
}