题目描述
输入
输出
样例输入
abaabaa样例输出
17 样例解释： f[2][a] = 1 f[3][a] = 1 f[4][a] = 1 f[4][b] = 2 f[5][a] = 1 f[5][b] = 2 f[6][a] = 3 f[7][a] = 4 f[7][b] = 2 以上为>0的f[][]，求和=17数据范围限制
这一篇同上一篇，都是从以前博客搬过来的，所以
真的是我的QWQ！之所以是截图是因为markdown丢了。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
ll nxt[1000010],n,ans,f[1000010][26];
char s[1000010];
void getNext(){
for(ll i=1,j=0;i<n;i++){
while(j>0 && s[i]!=s[j]) j=nxt[j-1];
if(s[i]==s[j]){
j++;
}
nxt[i]=j;
}
}
int main(){
scanf("%s",s);
n=strlen(s);
getNext();
for(ll x=1;x<n;x++){
for(char c='a';c<='z';c++){
if(c==s[nxt[x-1]]){
f[x][c-'a']=nxt[x-1]+1;
}
else{
f[x][c-'a']=f[nxt[x-1]][c-'a'];
}
ans+=f[x][c-'a'];
}
}
printf("%lld",ans);
}