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

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

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

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