badge：
这题瓶颈在于读题，充分展示了出题人的文学素养。
注意，我们以下讨论的所有前缀，都不包括字符串本身，即A不是A的前缀。
题意翻译出来就是，如果A是B的前缀，而且B是AA的前缀，那么A是B的“匹配前缀”。现在求一个字符串的所有前缀的最长的“匹配前缀”长度之和。
再来一遍：求一个字符串的/所有前缀的/最长的“匹配前缀”长度/之和。
这下是不是好受一些qwq。。
因为一个串的匹配前缀double一下能覆盖原串，所以它的匹配前缀一定是以原串的一个border作为前缀。
画个图可以知道，匹配前缀最长时，它所包含的原串的border最短。
那怎么求？我们知道KMP只能求最长border。
其实可以这样做：如果要求i位置之前的最短border，可以先计算next[i]，如果不为零则递归找next[next[i]]，如果还不为零再递归找next[next[next[i]]]，直到某一个位置next[k]是0了，那k就是最短border长度。
为啥？
如果next[k]=0，那么k位置是没有border的。还是画个图，你会发现如果j=next[i],k=next[j]，那么j的border k 同时也是i的border。
这就做完了。求出最短border长度之后，用串长减去后面那一段最短border，剩下的就是最长“匹配前缀”了。
可以用一个类似并查集路径压缩的思想加速递推。
记得long long。
#include<cstdio>
#include<cstring>
using namespace std;
char s[1000010];
long long nxt[1000010];
long long pos(long long x)
{
return nxt[x]==0?x:nxt[x]=pos(nxt[x]);
}
int main()
{
long long n,m,i,j,k,len,ans=0;
scanf("%lld",&len);
scanf("%s",s);
i=0;j=0;
nxt[0]=nxt[1]=0;
for(i=1;i<=len-1;i++)
{
while(j&&s[i]!=s[j])j=nxt[j];
if(s[i]==s[j])nxt[i+1]=++j;
else nxt[i+1]=0;
}
//for(i=0;i<=len;i++)printf("%d ",nxt[i]);
//printf("gocha
");
for(i=len;i>=1;i--)
{
ans+=i-pos(i);
}
printf("%lld
",ans);
return 0;
}
/*
8
babababa
*/