Note: This article is available in Chinese only. 本文暂无英文版本。
View original
是14年才被提出来的算法… 先%一下该算法的作者：作者的codeforces页
接下来，老规矩，放一波资料：
20171115 update:
emmmm，这篇是学习笔记是１６年９月写的。。。。一转眼13个月过去了啊。。
回文树，也叫回文自动机，简称PAM
学了SAM之后PAM简直是傻逼算法…
该算法时间和空间复杂度都是O(n)
这样的复杂度基于以下结论：
长度为n的字符串的本质不同的回文串的数目不超过n
因此状态数开到和字符串长度一样就可以了orz
len表示某个状态所表示的回文串的长度
cnt表示某个状态所表示的回文串的数量
构建PAM的算法仍然是增量算法，在某一时刻，本质不同的回文串的数量是sz-1 (sz标号从０开始，出去标号为０和标号为１的２个根)
唯一需要特别注意的是
在构建完PAM之后，沿着回文链（类比后缀链)从底向上跑一遍得到的cnt，才是真正的cnt
在构建完PAM之后，沿着回文链（类比后缀链)从底向上跑一遍得到的cnt，才是真正的cnt
在构建完PAM之后，沿着回文链（类比后缀链)从底向上跑一遍得到的cnt，才是真正的cnt
我的模板：
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月15日 星期三 20时31分58秒
4File Name :PAM.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23struct PAM
24{
25 //cnt表示某个节点的回文串的数量
26 //len表示的是该状态所表示的回文串的长度
27 //PAM有２个根，分别为状态０和状态１
28 //初２个根外，其余每个状态表示一个本质不同的回文串,总数为sz-1
29 struct state
30 {
31 int fail,cnt,len;
32 int nxt[26];
33 }st[N];
34 char S[N],RS[N];
35 int n,now,sz;
36 int Right[N];//Right[i]表示以i结尾的最长回文串的长度
37 int Left[N]; //Left[i]表示以i开头的最长回文串的长度...只需要倒序构建PAM就行了
38 void init()
39 {
40 ms(st,0);
41 now = 0 ;
42 st[0].fail = st[1].fail = 1;
43 st[1].len = -1;
44 sz = 1;
45 }
46 void extend(int c,int pos)
47 {
48 int p = now;
49 while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
50 if (!st[p].nxt[c]){
51 int np=++sz,q=st[p].fail;
52 st[np].len=st[p].len+2;
53 while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
54 st[np].fail=st[q].nxt[c];
55 st[p].nxt[c] = np;
56 }
57 now=st[p].nxt[c];
58 Right[pos] = st[now].len;
59 st[now].cnt++;
60 }
61 void Cnt() //构建之后跑cnt得到的才是真正的cnt
62 {
63 for ( int i = sz ; i >= 2; i--) st[st[i].fail].cnt += st[i].cnt;
64 }
65 void build ()
66 {
67 init();
68 int len = strlen(S+1);
69 for ( int i = 1 ; i <= len ; i++) extend(S[i]-'a',i);
70 }
71}A,B;
72int main()
73{
74#ifndef ONLINE_JUDGE
75 freopen("./in.txt","r",stdin);
76#endif
77
78#ifndef ONLINE_JUDGE
79 fclose(stdin);
80#endif
81 return 0;
82}