序列自动机

在阅读本文之前，请先阅读

自动机。

定义

序列自动机是接受且仅接受一个字符串的子序列的自动机。

本文中用 代指这个字符串。

状态

若 包含 个字符，那么序列自动机包含 个状态。

令 是 的一个子序列，那么 是 在 中第一次出现时末端的位置。

也就是说，一个状态 表示前缀 的子序列与前缀 的子序列的差集。

序列自动机上的所有状态都是接受状态。

转移

由状态定义可以得到，，也就是字符 下一次出现的位置。

为什么是“下一次”出现的位置呢？因为若 ，后缀 的子序列是后缀 的子序列的子集，一定是选尽量靠前的最优。

实现

从后向前扫描，过程中维护每个字符最前的出现位置：

这样构建的复杂度是 。

例题