[bzoj 3676][Apio2014]回文串

2021-06-21 01:03

阅读：482

标签：5.5 传送门 pap 出现 pre clu 关系 for using

传送门

Description

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。

Solution

回文树裸题，或者是“回文自动机”？

每个节点都是一个回文串，然后fail指针维护的是它的最大的后缀回文串（同时也是前缀的）。

回文树的用处？

——by \(PinkRabbit\)

统计每个本质不同回文串出现次数的。这个 Manacher 很难做到（需要配合后缀自动机），但是回文自动机可以解决。比如说本题。

有趣的是，回文自动机可以支持前端插入呢，只需要再维护一个指向最长回文前缀的指针 \(head\)就好啦。因为回文是两边对称的呢，所以前端插入也没关系的。注意两个指针要同时更新哦。

Code?

#include
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch1;i--)    
    {
        ans=max(ans,1ll*cnt[i]*len[i]);
        cnt[f[i]]+=cnt[i];    
    }
    printf("%lld\n",ans);
    return 0;
}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

[bzoj 3676][Apio2014]回文串

标签：5.5 传送门 pap 出现 pre clu 关系 for using

原文地址：https://www.cnblogs.com/PaperCloud/p/10252263.html

上一篇：Hibernate 之主键生成策略小总结

下一篇：本学期C#学习个人总结

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[bzoj 3676][Apio2014]回文串
文章链接：http://soscw.com/essay/96663.html

亲，登录后才可以留言！

[bzoj 3676][Apio2014]回文串

传送门

Description

Solution

Code?

评论

热门文章

推荐文章

最新文章

置顶文章