【bzoj3676】[Apio2014]回文串

2015年4月23日6,19115

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。

题解

用manacher找出本质不同的回文串,每个串在后缀自动机上查询出现次数

本质不同的回文串是能使mx增长的回文串

查询出现次数可以用倍增找出对应结点

刚A完就被人D飞了:“写什么马拉车+自动机”

然后就补了个回文自动机。。。

见 http://blog.csdn.net/u013368721/article/details/42100363。。。

然后此题是裸题

sam+manacher

pam

 

  • Tunix2015年4月28日 下午8:36 回复

    求问:对于数据qbabqcfbabf,答案应该是6吧(bab*2)?而不是应该是5……?

    #1  
    • hzwer2015年4月28日 下午9:01 回复
      admin

      是6啊。。。

      #11
      • Tunix2015年4月29日 上午9:39 回复

        回文自动机的做法……

        #12
        • hzwer2015年4月29日 上午9:47 回复
          admin

          是啊。。。

          #13
          • Tunix2015年4月29日 上午11:07

            QAQ那应该是我写的姿势不对……我学您的写法写的回文自动机AC了……但是跑出来是5……sorry麻烦您了

            #14
  • zld37949552015年6月23日 下午11:04 回复

    求教回文自动机QAQ

    #2  
  • mxh2015年8月5日 下午7:46 回复

    求教回文自动机

    #3  
  • 继续孤单2016年1月15日 上午10:21 回复

    学长求教为什么要倍增啊QAQ
    parent树上倍增要查询什么呢QAQ

    #4  
    • hzwer2016年1月15日 上午10:25 回复
      admin

      在parent树上找对应结点

      #41
      • 继续孤单2016年1月15日 上午10:27 回复

        嗯。。就是不用在自动机上跑一遍就可以找到它的位置是么QAQ

        #42
        • hzwer2016年1月15日 上午10:59 回复
          admin

          #43
          • 继续孤单2016年1月15日 上午11:08

            嗯嗯谢谢学长,麻烦学长了

            #44
  • %%%hzwer2016年5月11日 下午7:29 回复

    学长你的马拉车+sam算法有些问题dtddtddtddtddtddtddtddtddtddtddfddtddtddtddtdftddttdtddtddfddtddtddtddtddtddtddtddtddtddtddttdtdd
    这组应该187,代码跑的192

    #5  
  • modhzwer2016年6月1日 下午9:56 回复

    马拉车部分好像是有些问题的

    #6  
  • zkeh2016年12月18日 上午10:36 回复

    为什么马拉车字符串之间没有添其他符号啊

    #7