前缀和

给你一个字符串，求所有长度为偶数的前缀在整个字符串出现的次数和。

Input
共一行，一个字符串s。
Output
共一行，输出一个整数,代表长度为偶数的前缀在整个字符串出现的次数和。|S|≤200000。
Sample Input
abababc
Sample Output
6

Sol:

先用Kmp算法求出nex[]数组，建立fail树然后统计子树大小.

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200010
#define maxn 410000
using namespace std;
#define int long long
char s[N];
int nex[N],len,p[N],ans;
int pre[maxn],son[maxn],now[maxn],tot,col[maxn];
void con(int a,int b)
{
    pre[++tot]=now[a];
    now[a]=tot;
    son[tot]=b;
}
int dfs(int x) //统计子树大小 
{
    int sz=1;
    for(int p=now[x];p;p=pre[p])
        sz+=dfs(son[p]);
    return sz;
}
main(){
   scanf("%s",s+1);
   len=strlen(s+1);
   nex[1]=0;
        for(int i=2,j=0;i<=len;i++)
        {
            while(j && s[j+1]!=s[i]) 
            j=nex[j];
            if(s[j+1]==s[i]) 
                j++;
            nex[i]=j;//nex[8]=5
            con(j,i);//建一条边从j指向i,例如 5指向8,5是父亲点,8是子结点 
        }
   for(int i=1;i<=len;i++) 
        if(i%2==0)
            ans+=dfs(i);
   printf("%lld
",ans);
    
}

 更好的做法是这样的:

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200010
using namespace std;
char s[N];
int nex[N],len,p[N],ans;
int main(){
    scanf("%s",s+1);len=strlen(s+1);nex[1]=0;
    for(int i=2,j=0;i<=len;i++){
        while(j && s[j+1]!=s[i]) j=nex[j];
        if(s[j+1]==s[i]) j++;
        nex[i]=j;
    }
    for(int i=1;i<=len;i++) p[i]=1;
    for(int i=len;i>=1;i--)  //统计子树大小，从后向前面做
        p[nex[i]]+=p[i];
    for(int i=1;i<=len;i++) 
        
if(i%2==0) ans+=p[i];
    printf("%d
",ans);
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll o,p[200011],sum[200011],len,ans,j;
char a[200011];
int main()
{
	// scanf("%lld",&o);
	// while(o--)
	// {
	// 	memset(p,0,sizeof(p));
	// 	memset(sum,0,sizeof(sum));
		scanf("%s",a+1);
		len=strlen(a+1);
		ans=0;j=0;
		for(ll i=1;i<len;i++)
		{
			while(j&&a[j+1]!=a[i+1])
			    j=p[j];
			if(a[j+1]==a[i+1])
			    j++;
			p[i+1]=j;
		}
		for(ll i=1;i<=len;i++)
		if (i%2==0)
		     sum[i]=sum[p[i]]+1;
		else
		
		    sum[i]=sum[p[i]];
		    // ans+=sum[i];
                for(int i=1;i<=len;i++) ans+=sum[i];
		printf("%lld
",ans);
	// }
	return 0;
}