P3649 [APIO2014]回文串（回文树）

2021-04-01 08:25

阅读：542

标签：cout fine 模板题 efi 整数 define 字母 for 说明

题目描述

给你一个由小写拉丁字母组成的字符串 ss 。我们定义 ss 的一个子串的存在值为这个子串在 ss 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 ss ，求所有回文子串中的最大存在值。

输入输出格式

输入格式：

一行，一个由小写拉丁字母（a~z）组成的非空字符串 ss 。

输出格式：

输出一个整数，表示所有回文子串中的最大存在值。

输入输出样例

输入样例#1： 复制

abacaba

输出样例#1： 复制

输入样例#2： 复制

www

输出样例#2： 复制

说明

【样例解释1】

用 \(\lvert s \rvert\) 表示字符串 ss 的长度。

一个字符串 \(s_1\) \(s_2\) \(\dots\) \(s_{\lvert s \rvert}\) 的子串是一个非空字符串 \(s_i\) \(s_{i+1}\) \(\dots s_j\) ? ，其中 \(1\) \(\leq\) i \(\leq\) j \(\leq\) \(\lvert s \rvert\) 。每个字符串都是自己的子串。

一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。

这个样例中，有 7 个回文子串 a，b，c，aba，aca，bacab，abacaba。他们的存在值分别为 4, 2, 1, 6, 3, 5, 7 。

所以回文子串中最大的存在值为 77 。

第一个子任务共 8 分，满足1≤∣s∣≤100 。

第二个子任务共 15 分，满足1≤∣s∣≤1000 。

第三个子任务共 24 分，满足 1≤∣s∣≤10000 。

第四个子任务共 26 分，满足 1≤∣s∣≤100000 。

第五个子任务共 27 分，满足 1≤∣s∣≤300000 。

题解

这题没有什么好说的。
明显是回文树（也称回文自动机）的模板题。
我们只需要利用一下回文树的cnt数组，它表示的是当前回文串出现的次数，然后再与len数组相乘就OK了。len表示当前回文串的长度。

菜鸡代码

#include
#include
#include
#include
#include
#define ll long long
using namespace std;
struct node{
    int fail,ch[26],len,cnt;
}t[300100];
char s[300010];
int tot;
ll ans=0;
void solve()
{
    int len=strlen(s+1),k=0;s[0]='#';
    t[0].fail=t[1].fail=1;t[1].len=-1;tot=1;
    for(int i=1;iwhile(s[i-t[k].len-1]!=s[i])k=t[k].fail;
        if(!t[k].ch[s[i]-'a']){
            t[++tot].len=t[k].len+2;
            int j=t[k].fail;
            while(s[i-t[j].len-1]!=s[i])j=t[j].fail;
            t[tot].fail=t[j].ch[s[i]-'a'];
            t[k].ch[s[i]-'a']=tot;
        }
        k=t[k].ch[s[i]-'a'];
        t[k].cnt++;
    }
    for(int i=tot;i>=2;i--){
        t[t[i].fail].cnt+=t[i].cnt;
        if((long long)t[i].cnt*t[i].len>ans)
            ans=(long long)t[i].cnt*t[i].len;
    }
}

int main()
{
    cin>>s+1;
    int len=strlen(s+1);
    solve();
    coutreturn 0;
}

P3649 [APIO2014]回文串（回文树）

标签：cout fine 模板题 efi 整数 define 字母 for 说明

原文地址：https://www.cnblogs.com/hhh1109/p/9241104.html

上一篇：c#除掉字符串最后一个字符几种方法

下一篇：Windows 98 二十岁了，这些功能都是从它开始的（虽然 Windows 98 不如 Windows 95 那样具有革命性，但完成度更高，更加成熟。到最后还是：相见不如怀念。）

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

亲，登录后才可以留言！

P3649 [APIO2014]回文串（回文树）

题目描述

输入输出格式

输入输出样例

说明

题解

菜鸡代码

评论

热门文章

推荐文章

最新文章

置顶文章