本文主要是介绍#回文自动机#洛谷 3649 JZOJ 3654 回文串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
给你一个由小写拉丁字母组成的字符串 s s s。我们定义 s s s的一个子串的存在值为这个子串在 s s s中出现的次数乘以这个子串的长度。对于给你的这个字符串 s s s,求所有回文子串中的最大存在值。
分析
回文自动机模板,不解释
代码
#include <cstdio>
#include <cstring>
#define rr register
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=300011; char s[N]; int length,n; long long ans;
struct Trie{int trie[27],fail,len,s;};
struct PAM{Trie h[N]; int lst,cnt;inline void init(){h[0].len=h[1].fail=lst=0,h[0].fail=cnt=1,h[1].len=-1;}inline signed gail(int now){for (;s[n-h[now].len-1]^s[n];now=h[now].fail); return now;}inline void Insert(){rr int now=gail(lst);if (!h[now].trie[s[n]^96]){h[++cnt].len=h[now].len+2;rr int t=gail(h[now].fail);h[cnt].fail=h[t].trie[s[n]^96];h[now].trie[s[n]^96]=cnt;}lst=h[now].trie[s[n]^96];++h[lst].s;}
}pam;
inline void print(int ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
signed main(){scanf("%s",s+1),length=strlen(s+1);s[0]=96,pam.init();for (n=1;n<=length;++n) pam.Insert();for (rr int i=pam.cnt;i;--i){pam.h[pam.h[i].fail].s+=pam.h[i].s;ans=max(ans,1ll*pam.h[i].s*pam.h[i].len);}return !printf("%lld",ans);
}
这篇关于#回文自动机#洛谷 3649 JZOJ 3654 回文串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!