This is not the end.

0%

回文树

Posted on

关于算法名称

强调一下，虽然说它又叫回文自动机，但是它不是自动机！！！

1.它有多个初始状态。
2.它不能够“接受一个字符串”。

算法中的一些定义

回文自动机上，每个节点代表了一个回文子串。对每个节点记一个$len$，代表这个节点表示的回文子串的长度。

每个节点有一个转移集（边），边上有一个字符，指向这个节点表示的回文子串，在两边都加上这个字符后形成的回文子串。

每个节点有一个$fail$指针，这个节点表示的回文子串，最长的且在字符串中出现过的回文后缀，类似AC自动机失配指针，在构造的时候用于解决“失配”的问题。

回文树有两个初始状态，状态$0$和状态$1$。状态$0$表示长度为偶数的回文串的中心，也就是说，所有长度为2的回文串，都由$0$节点转移过来。因此有$len[0]=0$。状态$1$是为了方便构造长度为奇数的状态设计的，所有长度为1的回文串，都由状态1转移过来。因此$len[1]=-1$。显然还有$fail[0]=1$。因为如果加入一个字符，不能够形成长度为2的回文子串，那么就只能（并且一定能）形成长度为1的回文子串。

一些经常用来辅助解决问题的量：一个节点在$fail$树上的深度，就是这个串包含的回文串的个数；在插入一个字符的时候，对新到达的状态$sz++$，最后在$fail$树上，将一个点的儿子的$sz$累加起来，就是这个点表示的回文在字符串中出现的次数。

构造方法

首先初始化：

1
2
3
4
5
void init()
{
	ncnt=1,n=0; last=0;
	len[1]=-1,len[0]=0,S[0]=-1,fail[0]=1;
}

其中，$S$是在回文自动机内部存储下的插入的字符串，，$n$表示已经插入的字符串的长度。将$S[0]$设为一个不会出现的东西可以减少特判。$last$表示上一次插入字符到达的状态，初始设为$0$或者$1$都可以。

插入一个新字符$c$时，在$last$的$fail$树上找到深度最深的一个位置，使得这个位置表示的回文串可以通过加入$c$形成新的回文串。即这个串是$last$的回文后缀，并且满足这个串前面的第一个字符等于$c$，也就是$S[n-len[u]-1]==S[n]$。设这个位置为$cur$。如果这个节点都不存在新插入字符的转移，说明出现了新的本质不同的回文串，那么就需要新建节点。新节点的$len$等于$len[cur]+2$，新节点$fail$则是$fail$树上$cur$的祖先中第一个满足$S[n-len[u]-1]==S[n]$的节点的$c$字符的转移。如果没有这个转移，那么$fail$应该置为0。注意要先找$fail$，然后再在$cur$节点插入$c$的转移。因为对于$1$号节点的后继，节点的$fail$应该指向$0$。找到的第一个满足$S[n-len[u]-1]==S[n]$的$cur$的祖先是$1$，如果先插入转移，那么新节点的$fail$就会指向自己。先找$fail$，再插入从$cur$到$now$的转移可以避开这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Palindromic_Tree{
    int ch[N][26],fail[N],len[N],last;
    char S[N];
    int ncnt,n;
    void init()
    {
        n=0; S[0]=-1;
        ncnt=last=1;
        fail[1]=0,fail[0]=1,len[0]=0,len[1]=-1;
    }
    int get(int u){ while(S[n-len[u]-1]!=S[n]) u=fail[u]; return u;}
    void insert(int c)
    {
        S[++n]=c; int cur=get(last);
        if(!ch[cur][c])
        {
            int now=++ncnt; len[now]=len[cur]+2;
            fail[now]=ch[get(fail[cur])][c],ch[cur][c]=now;
        }
        last=ch[cur][c];
    }
}PT;

复杂度分析

设势能函数$\phi(i)$表示，插入前$i$个字符之后，已经插入的最长回文后缀的长度。

插入一个字符的时候$\phi(i)$最多+1，跳一次fail$\phi(i)$至少会-1，$\phi(i)$至多是$n$，所以构造的复杂度是$O(n)$。

Tricks

回文树上节点的数量 - 2 = 字符串中本质不同的回文串的数量。
一个节点在$fail$树上的深度 = 这个节点表示的回文串的回文后缀的数量。
得到一个回文串在字符串中出现的次数：$insert$的时候，在走到的那个节点（即这一步结束后的$last$）上令$sz++$，这是一个差分，意思是上$sz$到根的路径上的所有点$sz+=1$。最后将差分前缀和回去，即跑一遍$sz[fail[u]]+=sz[u]$即可得到每个节点表示的回文子串在原字符串中出现的次数。