又是一道回文自动机的好题
如果一个串是双倍回文串，一定满足两个条件
- 长度是4的倍数
- 有一个长度为它的长度一半的回文后缀
先预处理建立回文自动机，再枚举每一个节点
暴力跳$fail$指针，判断是否存在长度为它一半的回文后缀即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
using namespace std;
char s[500005];
int fail[500005];
int len[500005];
int ch[500005][26];
int n,ans,tot,last;
int () {
scanf("%d%s",&n,s+1);
tot=1;fail[0]=1;len[1]=-1;
for(register int i=1;i<=n;++i) {
while(s[i-len[last]-1]!=s[i]) last=fail[last];
if(!ch[last][s[i]-'a']) {
len[++tot]=len[last]+2;
int j=fail[last];
while(s[i-len[j]-1]!=s[i]) j=fail[j];
fail[tot]=ch[j][s[i]-'a'];
ch[last][s[i]-'a']=tot;
}
last=ch[last][s[i]-'a'];
}
for(register int i=tot;i;--i) {
int j=i;
if(len[i]%4>0||len[i]<=ans) continue ;
while((len[j]<<1)>len[i]) j=fail[j];
if(len[j]<<1==len[i]) ans=len[i];
}
printf("%dn",ans);
return 0;
}
|
近期评论