bzoj 3676: [Apio2014]回文串 — 回文自动机

  • 2017-12-22
  • 0
  • 0

 

3676: [Apio2014]回文串

Time Limit: 20 Sec  Memory Limit: 128 MB

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

emmm

回文自动机的入门题

就是建好回文自动机后用fail指针去更新size就好了

关于回文自动机的构造方法 https://chty.coding.me/2017/04/30/%E3%80%90%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0%E3%80%91%E5%9B%9E%E6%96%87%E8%87%AA%E5%8A%A8%E6%9C%BA/

 

评论

还没有任何评论,你来说两句吧