【luogu P5496】【模板】回文自动机(PAM)(回文树)

【模板】回文自动机(PAM)

题目链接:luogu P5496

题目大意

给你一个字符串,要你对于字符串的每个位置,求有多少个回文串是在这个位置结尾的。

思路

为啥要用 PAM

首先我们想想处理字符串问题有什么方法:
KMP、AC 自动机
后缀数组后缀自动机
Manacher
哈希、DP、暴力等等。

但你发现如果要处理回文串的问题,哈希+二分复杂度太高,Manacher 只能针对整个串,在面对这样的题的时候,似乎没有什么办法。
于是,就有了一个叫做 PAM 的东西。

PAM 有啥用

它可以求一个字符串的某个前缀中出现了多少个不同的回文串。
统计在一个字符串中每个回文串出现的次数。
(也就是说它可以求回文串的个数)

它还可以求以下标 \(i\) 结尾的回文串个数,也可以得出有哪些。

咋搞

那你同最后一个用处多多少少都能看出来,它是类似 AC 自动机一样的东西,有一个 \(fail\) 指针,指向的位置就是它失配之后跳转到的表示它最长后缀回文串的点。
然后接着它有一些数组:
\(len_i\) 表示第 \(i\) 个点表示的回文串的长度。
\(nxt_{i,j}\) 表示在第 \(i\) 个点表示的回文串两边都加 \(j\) 这个字符串形成的新回文串对于的点。(这个有点类似 Trie 数)
\(fail_i\) 就是我们前面说的失配指针。
\(sum_i\) 就是有多少个回文串的结束位置是它的结束位置。(这个就是用来求本题的答案啦)
\(num_i\) 在不处理的时候没有意义,在跑了 \(count()\) 函数之后,它就表示这个回文串在字符串中出现了多少次。
\(lst\) 就是以最后一个字符结尾的最长的回文串的编号。
有的时候,我们还会顺手维护一个 \(trans_i\),表示长度小于等于这个回文串的一半最长回文后缀。


回文树比较神奇的地方,就是它有两个根:\(0\) 表示偶数长度的根,\(1\) 表示奇数长度的根。
然后由于你可能跳 \(fail\) 边跳到空字符串之后可能会由原来的偶数长度变成奇数长度,所以 \(fail_0=1,fail_1=0\)。
然后我们设 \(len_0=0,len_1=-1\),至于为什么 \(len_1=-1\) 我们在后面会发现它的好处。

然后考虑在当前的字符串后面加一个字符,考虑怎么搞。
那首先肯定是跳 \(fail\) 边直到碰到可以匹配这个新字符串。
那你肯定会想如果一直都无法匹配,就要搞特判,但其实 \(len_1=-1\) 可以让我们不用特判。

首先不难想到判断是否能匹配是看 \(s_{n-len_{x}-1}\) 是否等于 \(s_n\)。(\(n\) 是当前字符串长度,\(x\) 是现在跳到的位置)
那如果一直无法匹配,就会跑到 \(1\),那这个时候带进去看:\(s_{n-len_x-1}\) 就是 \(s_{n-(-1)-1}\) 即 \(s_n\),所以自己肯定等于自己,就会跳出来。


接着就是匹配啦,那就会走到 \(nxt_{x,s_n}\),那如果有了我们就不用管,但如果没有这个点,那我们就要新开一个点 \(now\),并维护关系。
首先看 \(len_{now}\),那就是从 \(len_x\) 左右两边都加了 \(s_n\) 这个字符,长度就加了 \(2\)。
而且这个时候也不同特判,如果它自己一个形成回文串,那就是 \(len_{1}+2\),刚好就是 \(1\)。
接着你考虑维护 \(fail_{now}\),那跟 AC 自动机的维护方式一样,你先不断跳 \(fail\) 边找到 \(fail_x\) 可以匹配的,然后它两边加 \(s_n\) 这个字符对于的点就是 \(fail_{now}\) 了。
接着就是连 \(nxt_{x,s_n}\),这个就不多说了,\(nxt_{x,s_n}=now\)。有的时候还要记录父亲,这个也没什么麻烦的,直接 \(fa_{now}=x\) 即可。
然后是 \(sum_{now}\),那它其实就是比 \(fail_{now}\) 多了一种回文串(它自己),所以就是 \(sum_{fail_{now}}+1\)。

那接着是 \(trans_{now}\),那不难想到它也是类似 AC 自动机的匹配方式。
首先如果当前字符串的长度小于等于 \(2\),那它要么长度是 \(1\),要么是空,所以就直接 \(trans_{now}=fail_{now}\)。
那如果长的,那我们就考虑继续跳 \(fail\) 边,但是是从 \(trans_{x}\) 开始跳。(因为你只是要一半,你从 \(fail_x\) 开始跳就太慢了会超时)
那首先跳到的要能匹配 \(s_n\),接着就是要加上两边的两个 \(s_n\) 字符之后长度还不超过当前串的长度的一半,那跳到就退出,然后它匹配上 \(s_n\) 形成的回文串对于的点就是我们要的了。


这里再讲讲 \(count()\) 函数。
其实它就是从叶子到父亲不断的 DP 一下,因为如果一个 \(A\) 是 \(B\) 的子串,\(B\) 是 \(C\) 的子串,那 \(A\) 是 \(C\) 的子串。
所以在代码上就是倒序枚举点,然后 \(num_{fail_i}=num_{fail_i}+num_i\) 就可以了。

这道题

其实就是每次插入点,然后输出 \(sum_{lst}\) 即可。

代码

#include<cstdio>
#include<cstring>

using namespace std;

struct PAM {
	int len, nxt[26], fail, sum, num, trans;
}t[500002];
int sn, lastans, lst, tot, a[500001], n;
char s[500001];

int get_new(int l) {//建一个新的点
	t[++tot].len = l;
	for (int i = 0; i < 26; i++) t[tot].nxt[i] = 0;
	t[tot].fail = 0; t[tot].sum = 0; t[tot].num = 0; t[tot].trans = 0;
	return tot;
}

int get_fail(int x) {//像 AC 自动机一样匹配
	while (a[n - t[x].len - 1] != a[n]) x = t[x].fail;
	return x;
}

void insert(int x) {
	a[++n] = x;
	int cur = get_fail(lst);
	if (!t[cur].nxt[x]) {
		int now = get_new(t[cur].len + 2);//两边都扩展一格,所以长度加了 2
		t[now].fail = t[get_fail(t[cur].fail)].nxt[x];//建 fail 边
		t[cur].nxt[x] = now;//连儿子
		t[now].sum = t[t[now].fail].sum + 1;//后缀个数增加了它这个串
		if (t[now].len <= 2) t[now].trans = t[now].fail;//求 trans 数组
			else {
				int tmp = t[cur].trans;//也是像 AC 自动机一样跳 fail 边直到找到要的
				while (a[n - t[tmp].len - 1] != a[n] || ((t[tmp].len + 2) << 1) > t[now].len) tmp = t[tmp].fail;
				t[now].trans = t[tmp].nxt[x];
			}
	}
	lst = t[cur].nxt[x];
	t[lst].num++;//统计出现次数
}

void count() {//这个是求出这个回文串在这个字符串中出现的次数
	for (int i = tot; i >= 2; i--)
		t[t[i].fail].num += t[i].num;
}

int main() {
	scanf("%s", s + 1);
	sn = strlen(s + 1);
	
	lst = 0; t[0].len = 0; t[1].len = -1; tot = 2; a[0] = -1;//初始化
	t[1].fail = 0; t[0].fail = 1;//注意奇偶根的 fail 边是互相连着的
	for (int i = 1; i <= sn; i++) {
		insert((s[i] - 97 + lastans) % 26);
		lastans = t[lst].sum;
		printf("%d ", lastans);
	}
	
	return 0;
}
上一篇:Java中的密码生成器


下一篇:java – PBE:在尝试解密之前验证密码