大意
给定一个串,求出所有偶数长度的前缀在串中出现次数的总和
思路
首先我们知道有个东西叫 k m p kmp kmp
它有一个 n e x t next next数组,意思是:对于字符串 S S S的前 i i i个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作 n e x t [ i ] next[i] next[i]
发现跟上面那个玩意儿很像,但是上面那个要求是偶数的,所以我们只需要计算 i i i为偶数的情况然后求和即可
代码
#include<cstdio>
#include<cstring>
using namespace std;int kmp[200002],j,num[200002],n,ans;
char s[200002];
signed main()
{
scanf("%s",s);
n=strlen(s);
for(register int i=1;i<n;i++)//kmp模板
{
while(j&&s[i]!=s[j]) j=kmp[j];
j+=(s[i]==s[j]);
kmp[i+1]=j;
}
for(register int i=1;i<=n;i++)
{
if(!(i&1)) ans++,num[i]++;//是偶数的情况下多了一个子串
num[i]+=num[kmp[i]];//记得加上
ans+=num[kmp[i]];//同理
}
printf("%d",ans);//输出
}