bzoj 3676: [Apio2014]回文串【回文自动机】

回文自动机板子

或者是SAM+manacher+倍增，就是manacher求本质不同回文串（让f++的串），然后在SAM倍增查询对应点出现次数

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=300005;

int n,ch[N][27],fa[N],si[N],dis[N],la=1,con=1;

long long ans;

char s[N];

void ins(int c,int w)

{

	int p=la;

	for(;s[w-1-dis[p]]!=s[w];p=fa[p]);

	if(!ch[p][c])

	{

		int q=fa[p],cur=++con;

		for(;s[w-1-dis[q]]!=s[w];q=fa[q]);

		fa[cur]=ch[q][c],ch[p][c]=cur,dis[cur]=dis[p]+2;

	}

	si[la=ch[p][c]]++;

}

int main()

{

	scanf("%s",s+1);

	n=strlen(s+1);

	fa[0]=1,fa[1]=1,dis[1]=-1;

	for(int i=1;i<=n;i++)

		ins(s[i]-'a',i);

	for(int i=con;i>=1;i--)

		si[fa[i]]+=si[i];

	for(int i=1;i<=con;i++)

		ans=max(ans,1ll*dis[i]*si[i]);

	printf("%lld\n",ans);

	return 0;

}

巴特西

bzoj 3676: [Apio2014]回文串【回文自动机】

最新文章

热门文章