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

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

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

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

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

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

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

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

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

给你两个由小写英文字母组成的串 和 ，求：

的一个最短的子串，它不是 的子串；

的一个最短的子串，它不是 的子序列；

的一个最短的子序列，它不是 的子串；

的一个最短的子序列，它不是 的子序列。

令 表示在 A 的序列自动机中处于状态 ，在 B 的序列自动机中处于状态 ，需要再添加多少个字符能够不是公共子序列。