111qqz的小窝

老年咸鱼冲锋!

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

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

题意:

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

思路:

考虑回文自动机。

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

UPDATE: 弃用了这种代码风格,新的写法见下面。

那么sz-2就是本质不同的回文子串个数了orz(减掉2是因为PAM有2个根,这2个根不表示回文串)

 

对于新的代码风格,节点数标号是从0到siz,其中标号为0和标号为1的是2个根。

因此答案是siz-1

新的代码风格:

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz