概念

回文自动机，PAM，又叫回文树。

用于处理和回文子串有关的问题，和 SAM 有一些类似的地方。

构造

首先 PAM 上的每个结点代表原串的一个回文子串。

根据神秘结论，原串本质不同的回文子串至多有 \(n\) 个，也就是 PAM 的点数至多是 \(n + 2\)，边数至多是 \(n\).

考虑到回文串的奇偶性会导致一些讨论，考虑给奇数长度和偶数长度的回文子串分别构造奇根和偶根。

指针全部指向奇根，奇根长度为 \(-1\).

这样出现新字符的时候就可以直接挂到奇根。

然后考虑 PAM 上的转移。

从上到下的转移意味着在父结点代表的串中首尾各加上指定的字符。

从下到上的转移 fail 意味着该结点的最长回文真后缀对应的结点。

构造和 SAM 一样考虑增量，每次向上找到最后一个可以和当前位置匹配的结点转移就行。

向上跳相当于消耗已有的势能，势能分析得构造 PAM 的时间复杂度是 \(O(n)\).

有时候会需要知道某串中长度小于一半的回文子串，可以另外维护一个指针指向对应的子串。更新暴力向上跳就行。

void build() { cur = fail[0] = fail[1] = 1, len[1] = -1; }

int get_fail(int nd, int p)
{
	while (s[p - len[nd] - 1] != s[p]) nd = fail[nd];
	return nd;
}

void insert(int p)
{
	int x = get_fail(lst, p), c = ch_id(s[p]);
	if (!son[x][c])
	{
		cur++;
		len[cur] = len[x] + 2, fail[cur] = son[get_fail(fail[x], p)][c];
		son[x][c] = cur;
		if (len[cur] <= 2) trans[cur] = fail[cur];
		else
		{
			int tr = trans[x];
			while ((s[p - len[tr] - 1] != s[p]) || ((len[tr] + 2) * 2 > len[cur])) tr = fail[tr];
			trans[cur] = son[tr][c];
		}
	}
	lst = son[x][c], cnt[lst]++;
}

套路

本质不同回文子串个数

等价于 PAM 的总点数 - 2，也就是除去奇根和偶根。

回文子串出现次数

类似 SAM，考虑在回文树上求子树和。

回文树上 dp

例题：P4762 [CERC2014]Virus synthesis

考虑令 \(f[i]\) 表示构造回文树上结点 \(i\) 对应子串需要的最少次数，\(trans[i]\) 表示结点 \(i\) 长度不超过一半的最长回文真后缀结点。

讨论一下树边的转移和 trans 有关的转移就行。

k 阶回文子串计数

例题：CF835D Palindromic characteristics

考虑讨论 \(i\) 和 \(trans[i]\) 的长度转移。

咕咕咕，明天继续更。