回文自动机 (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\)。

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\)：

1. 找到一个最长的匹配，设当前前缀最长的回文后缀对应的状态为 \(now\)，则直接为 \(now\) 匹配 \(S_i\) 即可。

2. 新建状态（如果当前的回文子串还未出现过）。

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

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

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];
}

模板代码如下：

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,ACAM}\) 与 \(\text{Border}\) 的关系能够有更好的理解。