异或方程组

字符串 2

字符串 3

字符串 4

可持久化数组

主席树

拆点

SP1812

给定 $n$ 个串，求 $n$ 个串的 $\text{LCS}$。

先考虑两个串匹配的情况。考虑将一个串压入 $\text{SAM}$，另一个串在 $\text{SAM}$ 上匹配。

如果存在 $ch[pos][c]$，则直接匹配，且匹配长度 $+1$。否则考虑尽可能地保留后缀，于是不断跳 $\text{parent}$ 树。

由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于父节点等价类中最长串，于是当前串一定能与父节点最长串匹配。

于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，则跳到 $ch[pos][c]$ 结点，匹配长度变为 $len_\text{pos}+1$。

每次失配向上跳使得匹配长度变短，而匹配长度最多增加 $|T|$ 次，于是失配的均摊复杂度为 $O(1)$。时间复杂度 $O(|S|)$。

接下来考虑 $n$ 个串匹配的情况。先将一个串压入 $\text{SAM}$，其他所有串在 $\text{SAM}$ 上匹配。

对每个串，记录每个结点匹配的答案，然后每个结点取该结点所有匹配答案的最小值，然后所有结点的最大值即为所求答案。

注意 $\text{parent}$ 树的子节点可以将答案贡献给父节点，可以每次匹配后根据拓扑序转移答案。时间复杂度 $O(\sum |S|)$。