2014 Xi’An ACM-ICPC Regional Contest Problem G. The Problem to Slow Down You (回文自动机(模块化写法))

http://codeforces.com/gym/100548

题意:

切换面板:标签
标签
添加新标签

回文自动机、 给2个字符串,问2个字符串中,相等并且都是回文串的对数。

思路:

构建2个PAM.然后奇偶起点分别跑dfs即可。

PAM写成了模块化的形式orz

[crayon-[……]

Read more

ural 1960. Palindromes and Super Abilities (回文自动机,统计本质不同的回文串个数)

http://acm.timus.ru/problem.aspx?space=1&num=1960

题意:

给一个字符串S,依次输出字符串S的所有前缀中,本质不同的回文串个数。

思路:

考虑构建PAM是一个增量算法…所以一边构建一边输出答案就好了。。。

某一时刻本质不同的回文串个数就是[……]

Read more

hdu 3948 | 2011 Multi-University Training Contest 11 The Number of Palindromes (回文自动机模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=3948

题意:

给一个字符串,问本质不同的回文子串的个数。

思路:

考虑回文自动机。

我们知道,对于PAM上的一个节点,表示的就是一个本质不同的回文串。

UPDATE: 弃用了这种代码风格,新的写法见下[……]

Read more

UOJ #103. 【APIO2014】Palindromes (回文自动机模板题)

http://uoj.ac/problem/103

题意:

给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 s,求所有回文子串中的最大存在值。

思路:

回文自动机,也叫回文树,但其实并不是树2[……]

Read more