[SHOI2011]双倍回文

Posted on | In

又是一道回文自动机的好题

如果一个串是双倍回文串，一定满足两个条件

  • 长度是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
#include<bits/stdc++.h>
using namespace std;
char s[500005];
int fail[500005];
int len[500005];
int ch[500005][26];
int n,ans,tot,last;
int main() {
    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("%d\n",ans);
    return 0;
}