BZOJ3676: [Apio2014]回文串

2021-02-12 06:15

阅读：618

【传送门：BZOJ3676】

简要题意：

　　给出一个字符串，每一个回文子串的价值为这个回文子串出现的次数*回文子串的长度，求出价值最大的回文子串的价值

题解：

　　%%%又是一道新算法

　　本来想用AC自动机+马拉车搞一下的，结果不会

　　hzwer大佬的题解用了后缀自动机+马拉车

　　但是后缀自动机太难了

　　这时引出我们的新算法——回文树

　　算法详解，以及推荐代码风格

　　简单来说，回文树可以解决以下问题：

　　1.求串S前缀0~i内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同）
　　2.求串S内每一个本质不同回文串出现的次数
　　3.求串S内回文串的个数（其实就是1和2结合起来）
　　4.求以下标i结尾的回文串的个数

　　几乎很多回文问题均可解决

　　而这道题就是回文树裸题了，直接在加入节点是顺便统计一下个数，最后按fail边自下而上更新一下即可

参考代码：

#include
#include
#include
#include
#includeusing namespace std;
typedef long long LL;
struct Tree
{
    int len,fail,son[26];
}tr[310000];
char st[310000];
int len,last,tot,cnt[310000];
void ready()
{
    tr[0].len=0;tr[1].len=-1;
    tr[0].fail=1;
    tot=1;last=0;
}
int findfail(int i,int j)
{
    while(st[i-tr[j].len-1]!=st[i]) j=tr[j].fail;
    return j;
}
void add(int i,int x)
{
    int j=findfail(i,last);
    if(tr[j].son[x]==0)
    {
        tr[++tot].len=tr[j].len+2;
        tr[tot].fail=tr[findfail(i,tr[j].fail)].son[x];
        tr[j].son[x]=tot;
    }
    last=tr[j].son[x];
    cnt[last]++;
}
LL getans()
{
    LL ans=0;
    for(int i=tot;i>1;i--)
    {
        cnt[tr[i].fail]+=cnt[i];
        ans=max(ans,LL(tr[i].len)*LL(cnt[i]));
    }
    return ans;
}
int main()
{
    scanf("%s",st+1);
    len=strlen(st+1);
    ready();
    for(int i=1;i‘a‘);
    printf("%lld",getans());
}

上一篇：通过修改注册表设置windows环境变量

下一篇：win10 配置虚拟域名

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

亲，登录后才可以留言！

BZOJ3676: [Apio2014]回文串

【传送门：BZOJ3676】

简要题意：

题解：

参考代码：

评论

热门文章

推荐文章

最新文章

置顶文章