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个根不表示回文串）
1#include <iostream>
2#include <cstdio>
3#include <cstring>
4#include <algorithm>
5typedef long long LL;
6#define ri register int
7using namespace std;
8#define MAXALP 30
9#define ms(a,x) memset(a,x,sizeof(a))
10const int N = 3E5+7;
11struct PAM
12{
13 int cnt,len,fail;
14 int nxt[MAXALP];
15}st[N];
16int n, m, sz , last, cur;
17char s[N];
18inline int new_node(int x)
19{
20 st[sz].len = x; st[sz].cnt = 0;
21 ms(st[sz].nxt,0);
22 return sz++;
23}
24inline int get_fail(int x, int n)
25{
26 while(s[n-st[x].len-1] != s[n]) x = st[x].fail;
27 return x;
28}
29inline void pam_init()
30{
31 sz = 0 ;
32 new_node(0);
33 new_node(-1);
34 st[0].fail = 1;
35 ms(st[0].nxt,0);
36 last = 0;
37}
38void pam_insert( int c,int head)
39{
40 cur = get_fail(last,head);
41 if (!st[cur].nxt[c])
42 {
43 int nw = new_node(st[cur].len+2);
44 st[nw].fail = st[get_fail(st[cur].fail,head)].nxt[c];
45 st[cur].nxt[c] = nw;
46 }
47 last = st[cur].nxt[c];
48 st[last].cnt++;
49}
50int main()
51{
52// freopen("./in.txt","r",stdin);
53 int T;
54 int cas = 0 ;
55 cin>>T;
56 while (T--)
57 {
58 scanf("%s",s);
59 n = strlen(s);
60 pam_init();
61 for(int i=0;i<n;i++) pam_insert(s[i]-'a',i);
62 printf("Case #%d: %d\n",++cas,sz-2);
63 }
return 0;
}
对于新的代码风格，节点数标号是从0到siz,其中标号为0和标号为1的是2个根。
因此答案是siz-1
新的代码风格：
/* ***********************************************
Author :111qqz
Created Time :2017年11月14日 星期二 00时13分44秒
File Name :103.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define ms(a,x) memset(a,x,sizeof(a))
3typedef long long LL;
4using namespace std;
5const int N=3E5+7;
6struct PAM
7{
8 int fail,cnt,len;
9 int nxt[26];
10}st[N];
11char S[N];
12int n,now,sz;
13void pam_init()
14{
15 ms(st,0);
16 st[0].fail = st[1].fail = 1;
17 st[1].len = -1;
18 sz = 1;
19}
20void extend(int c,int pos)
21{
22 int p = now;
23 while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
24 if (!st[p].nxt[c]){
25 int np=++sz,q=st[p].fail;
26 st[np].len=st[p].len+2;
27 while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
28 st[np].fail=st[q].nxt[c];
29 st[p].nxt[c] = np;
30 }
31 now=st[p].nxt[c];
32 st[now].cnt++;
33}
34int main()
35{
36 int T,cas=0;
37 cin>>T;
38 while (T--)
39 {
40 scanf("%s",S);
41 pam_init();
42 for ( int i = 0 ,_=strlen(S); i < _ ; i++)
43 extend(S[i]-'a',i);
44 printf("Case #%d: %d\n",++cas,sz-1);
45 }
46 return 0;
47}