壹、什么是回文自动机

节点信息

其实就是 $\tt kmp$ 一样的东西……这个自动机里包含所有回文子串。

自动机边 $a\overset{c}{\rightarrow}b$ 表示字符串 $a$ 在首尾均添加字符 $c$ 将会得到 $b$ 。

你也可以大概想象成我们只存了回文串的后一半，自动机边就等于在后面加字符。

为啥跟 $\tt kmp$ 很像呢？因为我们要用 $f a i l$ 存储 最长回文后缀。其实 $f a i l$ 就是 $\rm border$ 啊！这个串本身是个回文串，所以回文后缀翻转过去就是一个回文前缀；反之，若其为 $\rm border$ ，翻转过来可知，其为回文串。所以 $f a i l$ 就是 $\rm border$ 。

初始节点

用节点 $0$ 表示空串，用节点 $1$ 表示 “ 反物质 $\times 1$ ” 。也就是说， $1$ 的儿子是长度为一的回文串。显然 $0$ 的儿子是长度为 $2$ 的回文串。

为了使 $l e n (s o n) = l e n (x) + 2$ 恒成立，令 $l e n (1) = - 1$ 即可。并且令 $f a i l (0) = 1$ 。

编号是可以随便定的，但是 $f a i l (0) = 1$ 很关键。因为 “ 反物质 ” 比空串还要短。

贰、构建自动机

初始化

int ch[MaxN][CharSiz], n = 0;int len[MaxN] = {   0,-1};int fail[MaxN] = {   1,1};char item[MaxN] = {   -1}; // hash 从 0 始则必须赋值为 -1

在线插入找不同

每次加入一个字符。那么自动机里将会增加一个现串的后缀。

如何找到？也就是旧串的回文后缀并且满足两边都是新加入字符。看代码就懂了。

int getFail(int x){   	while(item[n-len[x]-1] != item[n])		x = fail[x]; // keep jumping	return x; // index of node}

跳 $f a i l$ 完全跟 $\tt kmp$ 一个思路。代码中 $n$ 是现串的长度，也就是说， $i t e m [n]$ 是刚加入的字符。

如何保证其一定有结束呢？很简单，万川东到海， $f a i l$ 终至 $1$ ，而 $l e n (1) = - 1$ 就会结束循环。

插入新点

从代码来解释似乎简单一些。

int lst = 1, dep[MaxN];int cntNode = 1; // 0,1 is occupiedvoid add(char c){   	item[++ n] = c;	int cur = getFail(lst);	int now = ch[cur][c];	if(now == 0){   		now = ++ cntNode;		fail[now] = getFail(fail[cur]);		fail[now] = ch[fail[now]][c];		dep[now] = dep[fail[now]]+1;		len[now] = len[cur]+2; // obvious		ch[cur][c] = now; // must be here	}	lst = now; // update}

$l s t$ 表示旧串的最长回文后缀。先取到 $c u r$ 满足 $“ c + S t r (c u r) + c ”$ 是现串的最长回文后缀。然后查看是否已经有了该串。若没有，则需新开点，并获得其 $f a i l$ 值。

这里的 $f a i l$ 也很好获得，其实就是 $\tt kmp$ 的思路，用 $n o w$ 的父节点 $c u r$ 的 $f a i l$ 去更新。

$d e p$ 是沿着 $f a i l$ 链跳跃的深度，代表的是 以某个点为结尾的回文串数量。

注意 $c h$ 必须最后赋值。因为前面用到的 $c h [f a i l [n o w]] [c]$ 未必能保证 $fail[now]\ne cur$ 。若二者都是 $1$ ，那么你就凉了。

为什么不需要新开更多点？原因是，如果比 $S t r (n o w)$ 还要短，那么它就已经在前面出现过了。毕竟是回文串，利用 $S t r (n o w)$ 对称过去（如同 $\tt manacher$ 那般）就是旧串的子串。

时间复杂度

显然是 $\mathcal O(n)$ 的，跟 $\tt kmp$ 简直如出一辙。两个 $g e t F a i l$ 都会使得 $f a i l [n o w]$ 的深度减小。深度每次最多增大 $1$ 嘛。

叁、例题

洛谷板题

：没啥好说的，敲就完了。

#include 
   
     #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}const int MaxN = 500005;const int CharSiz = 26;namespace PAM{   	int ch[MaxN][CharSiz], n = 0;	int len[MaxN] = {   0,-1};	int fail[MaxN] = {   1,1};	char item[MaxN] = {   -1};	int getFail(int x){   		while(item[n-len[x]-1] != item[n])			x = fail[x]; // keep jumping		return x; // index of node	}	int lst = 1, dep[MaxN];	int cntNode = 1; // 0,1 is occupied	void add(char c){   		item[++ n] = c;		int cur = getFail(lst);		int now = ch[cur][c];		if(now == 0){   			now = ++ cntNode;			fail[now] = getFail(fail[cur]);			fail[now] = ch[fail[now]][c];			dep[now] = dep[fail[now]]+1;			len[now] = len[cur]+2; // obvious			ch[cur][c] = now; // must be here//			printf("ch[%d,%d] = %d, fail = %d\n",cur,c,now,fail[now]);		}		lst = now; // update	}	int query(){   		return dep[lst];	}}char xez[MaxN];int main(){   	scanf("%s",xez);	int yyds = strlen(xez);	for(int i=0,k=0; i

转载地址：http://chvq.baihongyu.com/

你可能感兴趣的文章