回文自动机 (PAM,Palindrome Automaton)

如果学习了$\text{AC}$自动机和后缀自动机($\text{SAM}$)，那么这个冷门算法其实非常简单

约定：原字符串为$S$，长度为$|S|$

结构介绍

自动机节点意义： $\text{PAM}$没有复杂的结构，每个节点对应了一种回文子串，节点个数$\leq |S|+2$

自动机的转移：$\text{PAM}$和$\text{AC}$自动机一样，有失配指针$fail$和匹配数组$nxt$

$fail_i$即是$i$的后缀的最长状态，$i$和$fail_i$的边构成了一棵树，但是这棵树有着两个根节点(?)，分别对应着长度为奇数/偶数的回文子串

每个转移$nxt_{i,j}$意味着在当前状态$i$的串两边增加字符$j$

但是由于$\text{PAM}$的构造是一个在线算法，所以如果想要像$\text{AC}$自动机一样每次转移直接访问$nxt$，需要结束后遍历结构

构造

为了便于访问，设偶数/奇数根分别为$0,1$，每个节点存储一个当前状态的长度$len$

特别的，$len_0=0,len_1=-1$(便于让所有的串都满足$len_{nxt_{i,j} }=len_i+2$)

同时让空串对应奇数根节点，把偶数根连向奇数，即$fail_0=1$，这样就只有一个根节点了

为了在线构造方便，$\text{PAM}$需要实现一个匹配函数$\text{Find}(x,y)$，即在当前$x$状态找到下一个位置$S_y$的匹配状态，如果失配则返回奇数根$1$

1
2
3
4
int Find(int x,int y){
    while(s[y]!=s[y-len[x]-1]) x=fail[x]; // 如果失配到了x=1,那么必然有s[y]=s[y]
    return x;
}

增加一个节点$S_i=c$

首先找到一个最长的匹配，设当前前缀最长的回文后缀对应的状态为$now$，则直接为$now$匹配$S_i$即可

然后是新建状态(如果当前的回文子串还未出现过)

和$\text{AC}$自动机类似，访问$fail$树上最近的匹配即可得到这个点的$fail$

需要注意的点是，因为当前节点可以是根节点，寻找$fail$必须在新建转移$nxt_{now,c}$之前进行，否则可能找到的$fail$是自己

1
2
3
4
5
6
7
8
void Extend(int i,int c){
    now=Find(now,i);
    if(!nxt[now][c]) {
        fail[++cnt]=nxt[Find(fail[now],i)][c];
		len[nxt[now][c]=cnt]=len[now]+2;
    }
    now=nxt[now][c];
}

模板代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
char s[N];
struct Palindrome_Automaton{
	int len[N],fail[N],nxt[N][26],now,cnt;
	void Init(){ 
        rep(i,0,cnt) memset(nxt,fail[i]=0,104);
		s[now=0]=len[1]=-1;
		fail[0]=fail[1]=cnt=1;
	}
	int Find(int x,int y){ 
		while(s[y-len[x]-1]!=s[y]) x=fail[x];
		return x;
	}
	void Extend(int i,int c){
		now=Find(now,i);
   		if(!nxt[now][c]) {
			fail[++cnt]=nxt[Find(fail[now],i)][c];
			len[nxt[now][c]=cnt]=len[now]+2;
    	}
    	now=nxt[now][c];
	}
};


拓展：回文串与$\text{Border}$

关于$\text{Border}$

推论1:回文串的$\text{Border}$也是回文串

若有回文串$S$的一个$\text{Border} :T$，则$S_{1,|T|}=S_{|S|-|T|+1,|S|}=reverse(S_{1,|T|})$

故$T$也是一个回文串

推论2:遍历回文自动机的$fail$链，能得到当前串的所有$\text{Border}$(基于推论1得到)

结合$\text{kmp,AC}$与$\text{Border}$的关系能够有更好的理解