【洛谷P3649】回文串

时间:2023-03-09 03:19:17
【洛谷P3649】回文串

题目大意:给定一个长度为 N 的字符串,定义一个变量为该字符串的回文子串长度乘以该字串出现的次数,求这个变量的最大值是多少。

题解:学会了回文自动机。

回文自动机是两棵树组成的森林结构,并通过 fail 指针构成一棵回文树结构。

回文树的节点存储的是每个子串的最长回文后缀,最长回文后缀的定义是:除了字串本身的最长的回文后缀。

可以证明回文树的节点数和边数是 \(O(|S|)\) 的。

建立回文树采用增量法,时间复杂度为 \(O(|S|)\)。

本题对于每个回文树节点,维护一个出现次数的变量。最后按照节点从后到前的顺序,将每个点的出现次数累加到其父节点(fail 节点)的出现次数中,并更新答案即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
typedef long long LL; char s[maxn];
int n; LL ans;
struct PAM{
int tot,last,trie[maxn][26],fail[maxn],len[maxn],sz[maxn];
PAM(){tot=1,fail[0]=fail[1]=1,len[1]=-1;}
void extend(int c,int i){
int p=last;
while(s[i-len[p]-1]!=s[i])p=fail[p];
if(!trie[p][c]){
int now=++tot,k=fail[p];
while(s[i-len[k]-1]!=s[i])k=fail[k];
len[now]=len[p]+2,fail[now]=trie[k][c],trie[p][c]=now;
}
last=trie[p][c],++sz[last];
}
void solve(){
for(int i=tot;i>1;i--){
sz[fail[i]]+=sz[i];
ans=max(ans,(LL)len[i]*sz[i]);
}
}
}pam; int main(){
scanf("%s",s+1),n=strlen(s+1);
for(int i=1;i<=n;i++)pam.extend(s[i]-'a',i);
pam.solve();
printf("%lld\n",ans);
return 0;
}