异或方程组

字符串 2

字符串 3

字符串 4

可持久化数组

主席树

拆点

SP1812

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

先考虑两个串匹配的情况。

考虑将一个串压入 $\text{SAM}$，其他所有串在 $\text{SAM}$ 上匹配。

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

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