洛谷 P3649 [APIO2014]回文串 回文树

题目描述

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

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

abacaba

输出样例#1：

7

输入样例#2：

www

输出样例#2：

4

说明

【样例解释1】

用 ∣ s ∣ |s| ∣s∣ 表示字符串 s s s 的长度。

一个字符串 s 1 s 2 … s ∣ s ∣ s_1 s_2 \dots s_{\lvert s \rvert} s1​s2​…s∣s∣​ 的子串是一个非空字符串 s i s i + 1 … s j s_i s_{i+1} \dots s_j si​si+1​…sj​，其中 1 ≤ i ≤ j ≤ ∣ s ∣ 1≤i≤j≤|s| 1≤i≤j≤∣s∣。每个字符串都是自己的子串。

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

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

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

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

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

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

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

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

分析：

直接把回文树建出来。出现次数就是以 i i i结尾的最长回文串的位置+1，然后dp累加一下就可以得到出现次数了。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define LL long long

const int maxn=3e5+7;

using namespace std;

char s[maxn];
int n,cnt,top[maxn];
LL ans;

struct node{
    int fail,len,sum;
    int son[26];
}t[maxn];

bool cmp(int x,int y)
{
    return t[x].len>t[y].len;
}

void build()
{
    cnt=1;
    t[0].fail=1;
    t[0].len=0;
    t[1].fail=0;
    t[1].len=-1;
    LL now=1;
    for (LL i=1;i<=n;i++)
    {
        while (s[i]!=s[i-t[now].len-1]) now=t[now].fail;
        if (!t[now].son[s[i]-'a'])
        {
            cnt++;
            LL k=t[now].fail;
            while (s[i]!=s[i-t[k].len-1]) k=t[k].fail;
            t[cnt].fail=t[k].son[s[i]-'a'];
            t[now].son[s[i]-'a']=cnt;
            t[cnt].len=t[now].len+2;
        }
        now=t[now].son[s[i]-'a'];
        t[now].sum++;
    }  
    for (int i=1;i<=cnt;i++) top[i]=i;
    sort(top+1,top+cnt+1,cmp);
    for (int i=1;i<=cnt;i++)
    {
        int x=top[i];
        t[t[x].fail].sum+=t[x].sum;
        ans=max(ans,(LL)t[x].sum*(LL)t[x].len);
    }
}

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    build();
    printf("%lld",ans);
}