BZOJ3676 [Apio2014]回文串 回文自动机

发布于 2017-09-18  6.13k 次阅读


[toggle hide="yes" title="题目" color=""]

Description

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

Input

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

Output

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

Sample Input

【样例输入1】

abacaba

【样例输入2】

www
Sample Output

【样例输出1】

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次,其出现值为1:1:1=1
● 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。

[/toggle]

回文自动机裸题。

空间复杂度:O(n*(字符集大小)),时间复杂度:O(n*log(字符集大小))。

可实现的操作:

1.求字符串前缀中本质不同的回文串的个数。

2.求每一个本质不同回文串出现的次数。

3.求所有的回文串数。

4.求以特定下标为结尾的回文串数。

同时求出回文串的长度。

直接上代码,具体不解释。注意,新建节点、计算fail指针时顺序一定不能错,一定要先计算好fail指针再建新的子节点

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974