回文自动机学习笔记

回文自动机是个处理回文串有关问题的一个犀利的数据结构。它是一个树形结构。每个节点包括以下信息：
(1)len[i]表示编号为i的节点表示的回文串的长度(一个节点表示一个回文串)
(2)next[i][c]表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的的节点的编号
(3)fail[i]指向的节点表示的回文串是i节点表示回文串的一个最长后缀(当然它也是一个回文串了)
(4)cnt[i]表示节点i表示的本质不同的串的个数(建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的)
(5)num[i]表示以节点i表示的回文串的最右端点为回文串结尾的回文串个数(有点拗口哦)。
(6)last指向新添加一个字母后所形成的最长回文串表示的节点。
(7)S[i]表示第i次添加的字符(一开始设S[0]=-1,表示一个在串S中不会出现的字符)。
(8)p表示添加的节点个数。
(9)n表示添加的字符个数。

初始时，回文树有两个节点，0表示偶数长度串的根和1表示奇数长度串的根,且len[0]=0，len[1]=-1,last=0,S[0]=-1,n=0,p=2(添加了节点0、1)。如下图所示

假设现在我们有串S=abbaabba。
首先我们添加第一个字符'a'，S[++n]='a',然后判断此时S[n-len[last]-1]是否等于S[n]，即上一个串前一个的位置的字符和新添加的位置字符是否相同，相同则说明构成回文。否则，last=fail[last]。此时last=0，此时S[1-0-1]!=S[1]，所以last=fail[last]=1，然后我们发现S[1-(-1)-1]==S[1]（即自己等于自己，所以我们让len[1]等于-1可以让这一步更加方便）。

令cur等于此时的last（即cur=last=1),判断此时next[cur]['a']是否已经有后继，如果next[cur]['a']没有后继，我们就进行如下的步骤：新建节点(节点数p++，且之后p=3），并让now等于新节点的编号（now=2），则len[now]=len[cur]+2（每一个回文串的长度总是在其最长子回文串的基础上在两边加上两个相同的字符构成的，所以是加2，同时体现出我们让len[1]=-1的优势，一个字符自成一个奇回文串时回文串的长度为(-1)+2=1）。
然后我们让fail[now]=next[get_fail(fail[cur])]['a']，即得到fail[now]（此时为fail[2]=0),其中的get_fail函数就是让找到第一个使得S[n-len[x]-1]==S[n]的x，并且x是cur的祖辈节点。然后next[cur]['a']=now。

当上面步骤完成后我们让last=next[cur][c],然后cnt[last]++。

此时回文树为下图状态：

接着插入第二个字符'b'

接着插入第三个字符'b'

接着插入第四个字符'a'

接着插入第五个字符'a'

接着插入第六个字符'b'

接着插入第七个字符'b'

接着插入第八个字符'a'

 1 struct PalindTeee
 2 {
 3     int next[N][26];
 4     int fail[N],cnt[N],num[N],len[N],S[N];
 5     int last,n,p;
 6 
 7 
 8     int newNode(int l)
 9     {
10         clr(next[p],0);
11         cnt[p]=num[p]=0;
12         len[p]=l;
13         return p++;
14     }
15 
16     void init()
17     {
18         p=0; newNode(0); newNode(-1);
19         last=n=0;
20         S[n]=-1; fail[0]=1;
21 
22     }
23 
24     int getFail(int x)
25     {
26         while(S[n-len[x]-1]!=S[n]) x=fail[x];
27         return x;
28     }
29 
30     void add(int c)
31     {
32         c-='a';
33         S[++n]=c;
34         int cur=getFail(last);
35         if(!next[cur][c])
36         {
37             int now=newNode(len[cur]+2);
38             fail[now]=next[getFail(fail[cur])][c];
39             next[cur][c]=now;
40             num[now]=num[fail[now]]+1;
41         }
42         last=next[cur][c];
43         cnt[last]++;
44     }
45 
46     void count()
47     {
48         for(int i=p-1;i>=0;i--) cnt[fail[i]]+=cnt[i];
49     }
50 
51 };

如果为了省空间，可以换成链表的形式。

 1 struct PalindTeee
 2 {
 3     vector&lt;pair&lt;int,int&gt; &gt; next[N];
 4     int fail[N],cnt[N],num[N],len[N],S[N];
 5     int last,n,p;
 6 
 7 
 8     int newNode(int l)
 9     {
10         next[p].clear();
11         cnt[p]=num[p]=0;
12         len[p]=l;
13         return p++;
14     }
15 
16     void init()
17     {
18         p=0; newNode(0); newNode(-1);
19         last=n=0;
20         S[n]=-1; fail[0]=1;
21 
22     }
23 
24     int getFail(int x)
25     {
26         while(S[n-len[x]-1]!=S[n]) x=fail[x];
27         return x;
28     }
29 
30     int getId(int cur,int c)
31     {
32         for(int i=0;i&lt;next[cur].size();i++) if(next[cur][i].first==c)
33         {
34             return next[cur][i].second;
35         }
36         return 0;
37     }
38 
39     void add(int c)
40     {
41         c-='a';
42         S[++n]=c;
43         int cur=getFail(last);
44 
45         if(!getId(cur,c))
46         {
47             int now=newNode(len[cur]+2);
48 
49             fail[now]=getId(getFail(fail[cur]),c);
50             next[cur].pb(MP(c,now));
51             num[now]=num[fail[now]]+1;
52         }
53         last=getId(cur,c);
54         cnt[last]++;
55     }
56 
57     void count()
58     {
59         for(int i=p-1;i>=0;i--) cnt[fail[i]]+=cnt[i];
60     }
61 };