[APIO2014]回文串

Posted on | In

因为最近沉迷搞学科所以没有半个月没有更博

毫无疑问这题最简单的做法应该是回文自动机

暴力跳$fail$指针再顺便统计一下节点的个数

最后取最大值即可，就是一道$PAM$模板题

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
31
#include<bits/stdc++.h>
using namespace std;
char s[300003];
int n,tot,last;
int cnt[300003];
int len[300003];
int fail[300003];
int ch[300003][26];
long long ans;
int main() {
    scanf("%s",s+1);n=strlen(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'];
        ++cnt[last];
    }
    for(register int i=tot;i>=2;--i) {
        cnt[fail[i]]+=cnt[i];
        ans=max(ans,(long long)len[i]*(long long)cnt[i]);
    }
    printf("%lld\n",ans);
    return 0;
}