P4287 [SHOI2011]双倍回文

题意

考虑对每个节点\(x\)维护\(lastpos_x\)表示\(x\)的所有后缀回文串中第一个\(len\leqslant len_x/2\)并且能和\(x\)最后一个字符匹配的，之后枚举节点，判断该点回文串是否合法。

求\(lastpos_x\)：

如果新建节点\(x\)满足\(len_x\leqslant 2\)，那么\(lastpos_x=fail_x\)。

不然则从\(x\)的父亲节点向上跳，边跳边判断即可。

code:

#include<bits/stdc++.h>

using namespace std;

const int maxn=500010;

int n,ans;

char s[maxn];

struct PA

{

	int last,tot;

	int fail[maxn],len[maxn],lastpos[maxn];

	int ch[maxn][30];

	PA(){tot=1;fail[0]=1;len[1]=-1;}

	inline int getfail(int x,int pos,char* s)

	{

		s[0]='#';

		while(s[pos-len[x]-1]!=s[pos])x=fail[x];

		return x;

	}

	inline void build(char* s,int n)

	{

		s[0]='#';

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

		{

			int c=s[i]-'a';

			int p=getfail(last,i,s);

			if(!ch[p][c])

			{

				int q=++tot;len[q]=len[p]+2;

				int tmp=getfail(fail[p],i,s);

				fail[q]=ch[tmp][c];ch[p][c]=q;

				if(len[q]<=2)lastpos[q]=fail[q];

				else

				{

					tmp=lastpos[p];

					while(s[i-len[tmp]-1]!=s[i]||((len[tmp]+2)<<1)>len[q])tmp=fail[tmp];

					lastpos[q]=ch[tmp][c];

				}

			}

			last=ch[p][c];

		}

	}

}pa;

int main()

{

	//freopen("test.in","r",stdin);

	//freopen("test.out","w",stdout);

	scanf("%d%s",&n,s+1);

	pa.build(s,n);

	for(int i=2;i<=pa.tot;i++)

		if((pa.len[pa.lastpos[i]]<<1)==pa.len[i]&&pa.len[pa.lastpos[i]]%2==0)

			ans=max(ans,pa.len[i]);

	printf("%d",ans);

	return 0;

}

巴特西

P4287 [SHOI2011]双倍回文

题意

最新文章

热门文章