BZOJ 3676: [Apio2014]回文串

时间：2023-01-05 04:46:43

3676: [Apio2014]回文串

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 2013  Solved: 863
[Submit][Status][Discuss]

Description

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

Input

输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。

Output

输出一个整数，为逝查回文子串的最大出现值。

Sample Input

【样例输入l】
abacaba

【样例输入2]
www

Sample Output

【样例输出l】
7

【样例输出2]
4

HINT

一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。

在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中：

● a出现4次，其出现值为4：1：1=4

● b出现2次，其出现值为2：1：1=2

● c出现1次，其出现值为l：1：l=l

● aba出现2次，其出现值为2：1：3=6

● aca出现1次，其出现值为1=1：3=3

●bacab出现1次，其出现值为1：1：5=5

● abacaba出现1次，其出现值为1：1：7=7

故最大回文子串出现值为7。

【数据规模与评分】

数据满足1≤字符串长度≤300000。

Source

 

[Submit][Status][Discuss]

去这里自学了一下回文自动机（回文树？），赶脚贼牛逼 ( ఠൠఠ )ﾉ。然后，就真的是裸题了，23333.

当然，如果不用回文自动机也是可以做的。首先用Manacher求出来所有本质不同的回文子串，然后只需要知道每个在原串中出现的次数即可。方法有二，要么后缀数组，要么后缀自动机。后缀自动机的话好像需要倍增，添个$log$不是什么问题？后缀数组的话也需要二分+ST表，还是要添个$log$。

 #include <cstdio>

 namespace Pal

 {

     const int siz = ;

     int next[siz][];

     int fail[siz];

     int cnt[siz];

     int len[siz];

     int str[siz];

     int last;

     int tot;

     int n;

     inline int node(int l)

     {

         len[tot] = l;

         return tot++;

     }

     inline void init(void)

     {

         node();

         node(-);

         last = ;

         str[] = -;

         fail[] = ;

     }

     inline int getFail(int t)

     {

         while (str[n - len[t] - ] != str[n])

             t = fail[t];

         return t;

     }

     inline void insert(int c)

     {

         str[++n] = c;

         int cur = getFail(last), now;

         if (!next[cur][c])

         {

             now = node(len[cur] + );

             fail[now] = next[getFail(fail[cur])][c];

             next[cur][c] = now;

         }

         ++cnt[last = next[cur][c]];

     }

     inline void count(void)

     {

         for (int i = tot - ; ~i; --i)

             cnt[fail[i]] += cnt[i];

     }

     inline long long answer(void)

     {

         long long ret = ;

         for (int i = tot - ; i > ; --i)

             if (ret < (long long)len[i] * cnt[i])

                 ret = (long long)len[i] * cnt[i];

         return ret;

     }

 }

 const int siz = ;

 char s[siz];

 signed main(void)

 {

     scanf("%s", s);

     Pal::init();

     for (char *t = s; *t; ++t)

         Pal::insert(*t - 'a');

     Pal::count();

     printf("%lld\n", Pal::answer());

 }

@Author: YouSiki

相关文章