PAM

Luogu 3649(注意一下所有回文串个数是咋统计的)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300005;
char s[N];
ll fa[N],len[N],size[N],ch[N][30],cnt=1,last,ans;
int addnode(int x)
{
	cnt++;
	len[cnt]=x;
	return cnt;
}
void add(int pos,int c)
{
	int u=last;//取出last 
	while(s[pos-len[u]-1]!=s[pos]) u=fa[u]; 
	if(!ch[u][c])
	{
		int now=addnode(len[u]+2);
		int v=fa[u];
		while(s[pos-len[v]-1]!=s[pos]) v=fa[v];
		fa[now]=ch[v][c];
		ch[u][c]=now;
	}
	last=ch[u][c];size[last]++;
}
int main()
{
	fa[0]=1,fa[1]=0;
	len[1]=-1,len[0]=0;
	scanf("%s",s+1);
	ll lenn=strlen(s+1); 
	for(int i=1;i<=lenn;i++) add(i,s[i]-'a');
	for(int i=cnt;i;i--) size[fa[i]]+=size[i],ans=max(ans,len[i]*size[i]);
	printf("%lld",ans);
}

Luogu 4287(注意一下你要知道遍历fail边就是遍历以这个字符为后缀的所有回文串)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005;
char s[N];
int fa[N],len[N],size[N],ch[N][30],cnt=1,last,ans,pre[N][30],mk[N],re[30],L[N];
int addnode(int x)
{
	cnt++;
	len[cnt]=x;
	return cnt;
}
void add(int pos,int c)
{
	ll u=last;//??last 
	while(s[pos-len[u]-1]!=s[pos]) u=fa[u]; 
	if(!ch[u][c])
	{
		ll now=addnode(len[u]+2);
		ll v=fa[u];
		while(s[pos-len[v]-1]!=s[pos]) v=fa[v];
		fa[now]=ch[v][c];
		ch[u][c]=now;
		if(len[now]%4==0)
		{
			int pp=len[now]/2;
			int ree=L[pos-pp],f=0;
			while(1)
			{
				if(ree==0||ree==1)
				break;
				if(len[ree]==pp)
				{
					f=1;
					break;
				}
				ree=fa[ree];
			}
			if(f) ans=max(ans,len[now]);
		}
//		cout<<now<<" "<<mk[now]<<endl;
	}
	last=ch[u][c];size[last]++,L[pos]=last;
}
int main()
{
	fa[0]=1,fa[1]=0;
	len[1]=-1,len[0]=0;
	ans=0;
	int nn;
	scanf("%d",&nn);
	scanf("%s",s+1);
	ll lenn=strlen(s+1); 
	for(int i=1;i<=lenn;i++) add(i,s[i]-'a');
	printf("%d",ans);
}

JSK Colorful String (https://nanti.jisuanke.com/t/41389)
直接暴力啊，记录一个前缀和数组直接暴力找每个串的不同字符然后记录,因为只有26个小写字母

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400005;
char s[N];
ll fa[N],len[N],size[N],ch[N][30],cnt=1,last,ans,pre[N][30],mk[N],re[30];
int addnode(int x)
{
	cnt++;
	len[cnt]=x;
	return cnt;
}
void add(int pos,int c)
{
	ll u=last;//??last 
	while(s[pos-len[u]-1]!=s[pos]) u=fa[u]; 
	if(!ch[u][c])
	{
		ll now=addnode(len[u]+2);
		ll v=fa[u];
		while(s[pos-len[v]-1]!=s[pos]) v=fa[v];
		fa[now]=ch[v][c];
		ch[u][c]=now;
		ll jk=0;
		for(int j=0;j<26;j++) re[j]=pre[pos][j]-pre[pos-len[now]][j];
		for(int j=0;j<26;j++) if(re[j]>0) jk++;
		mk[now]=jk;
//		cout<<now<<" "<<mk[now]<<endl;
	}
	last=ch[u][c];size[last]++;
}
int main()
{
	fa[0]=1,fa[1]=0;
	len[1]=-1,len[0]=0;
	ans=0;
	scanf("%s",s+1);
	ll lenn=strlen(s+1); 
	for(int i=1;i<=lenn;i++)
	{
		for(int j=0;j<26;j++) pre[i][j]=pre[i-1][j];
		pre[i][s[i]-'a']++;
	}
	for(int i=1;i<=lenn;i++) add(i,s[i]-'a');
	for(int i=cnt;i;i--) size[fa[i]]+=size[i];
	for(int i=2;i<=cnt;i++) ans+=size[i]*mk[i];
	printf("%lld",ans);
}