3676: [Apio2014]回文串

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 2013  Solved: 863

[][][]

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

 

[ ][ ][ ]

 

 

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

 

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

 

1 #include 
     
       2  3 namespace Pal 4 { 5     const int siz = 1000005; 6     int next[siz][26]; 7     int fail[siz]; 8     int cnt[siz]; 9     int len[siz];10     int str[siz];11     int last;12     int tot;13     int n;14     15     inline int node(int l)16     {17         len[tot] = l;18         return tot++;19     }20     21     inline void init(void)22     {23         node(0);24         node(-1);25         last = 0;26         str[0] = -1;27         fail[0] = 1;28     }29     30     inline int getFail(int t)31     {32         while (str[n - len[t] - 1] != str[n])33             t = fail[t];34         return t;35     }36     37     inline void insert(int c)38     {39         str[++n] = c;40         int cur = getFail(last), now;41         if (!next[cur][c])42         {43             now = node(len[cur] + 2);44             fail[now] = next[getFail(fail[cur])][c];45             next[cur][c] = now;46         }47         ++cnt[last = next[cur][c]];48     }49     50     inline void count(void)51     {52         for (int i = tot - 1; ~i; --i)53             cnt[fail[i]] += cnt[i];54     }55     56     inline long long answer(void)57     {58         long long ret = 0;59         60         for (int i = tot - 1; i > 1; --i)61             if (ret < (long long)len[i] * cnt[i])62                 ret = (long long)len[i] * cnt[i];63                 64         return ret;65     }66 }67 68 const int siz = 300005;69 70 char s[siz];71 72 signed main(void)73 {74     scanf("%s", s);75     76     Pal::init();77     78     for (char *t = s; *t; ++t)79         Pal::insert(*t - 'a');80         81     Pal::count();82     83     printf("%lld\n", Pal::answer());84 }
     

 

@Author: YouSiki