序列自动机

字符串 / seq-automaton

本地源文件：docs/string__seq-automaton.md

序列自动机

在阅读本文之前，请先阅读 自动机．

定义

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

本文中用 𝑠s 代指这个字符串．

状态

若 𝑠s 包含 𝑛n 个字符，那么序列自动机包含 𝑛 +1n+1 个状态．

令 𝑡t 是 𝑠s 的一个子序列，那么 𝛿(𝑠𝑡𝑎𝑟𝑡,𝑡)δ(start,t) 是 𝑡t 在 𝑠s 中第一次出现时末端的位置．

也就是说，一个状态 𝑖i 表示前缀 𝑠[1..𝑖]s[1..i] 的子序列与前缀 𝑠[1..𝑖 −1]s[1..i−1] 的子序列的差集．

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

转移

由状态定义可以得到，𝛿(𝑢,𝑐) =min{𝑖|𝑖 >𝑢,𝑠[𝑖] =𝑐}δ(u,c)=min{i|i>u,s[i]=c}，也就是字符 𝑐c 下一次出现的位置．

为什么是「下一次」出现的位置呢？因为若 𝑖 >𝑗i>j，后缀 𝑠[𝑖..|𝑠|]s[i..|s|] 的子序列是后缀 𝑠[𝑗..|𝑠|]s[j..|s|] 的子序列的子集，一定是选尽量靠前的最优．

实现

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

1𝐈𝐧𝐩𝐮𝐭. A string 𝑆2𝐎𝐮𝐭𝐩𝐮𝐭. The state transition of the sequence automaton of 𝑆3𝐌𝐞𝐭𝐡𝐨𝐝. 4𝐟𝐨𝐫 𝑐∈Σ5𝑛𝑒𝑥𝑡[𝑐]←𝑛𝑢𝑙𝑙6𝐟𝐨𝐫 𝑖←|𝑆| 𝐝𝐨𝐰𝐧𝐭𝐨 17𝑛𝑒𝑥𝑡[𝑆[𝑖]]←𝑖8𝐟𝐨𝐫 𝑐∈Σ9𝛿(𝑖−1,𝑐)←𝑛𝑒𝑥𝑡[𝑐]10𝐫𝐞𝐭𝐮𝐫𝐧 𝛿1Input. A string S2Output. The state transition of the sequence automaton of S3Method. 4for c∈Σ5next[c]←null6for i←|S| downto 17next[S[i]]←i8for c∈Σ9δ(i−1,c)←next[c]10return δ

这样构建的复杂度是 𝑂(𝑛|Σ|)O(n|Σ|)．

例题

「HEOI2015」最短不公共子串

给你两个由小写英文字母组成的串 𝐴A 和 𝐵B（1 ≤|𝐴|,|𝐵| ≤20001≤|A|,|B|≤2000），求：

  1. 𝐴A 的一个最短的子串，它不是 𝐵B 的子串；
  2. 𝐴A 的一个最短的子串，它不是 𝐵B 的子序列；
  3. 𝐴A 的一个最短的子序列，它不是 𝐵B 的子串；
  4. 𝐴A 的一个最短的子序列，它不是 𝐵B 的子序列．

题解

题目的 1 和 3 两问需要后缀自动机，而且做法类似，在这里只讲解 2 和 4 两问．

第 2 问比较简单，枚举 A 的子串输入进 B 的序列自动机，若不接受则计入答案．

第 4 问需要 DP．令 𝑓(𝑖,𝑗)f(i,j) 表示在 A 的序列自动机中处于状态 𝑖i，在 B 的序列自动机中处于状态 𝑗j，需要再添加多少个字符能够不是公共子序列．状态转移方程为：

𝑓(𝑖,𝑗)=min𝛿𝐴(𝑖,𝑐)≠𝑛𝑢𝑙𝑙𝑓(𝛿𝐴(𝑖,𝑐),𝛿𝐵(𝑗,𝑐))+1.f(i,j)=minδA(i,c)≠nullf(δA(i,c),δB(j,c))+1.

转移起点为 𝑓(𝑖,𝑛𝑢𝑙𝑙) =0f(i,null)=0．

参考代码

---|---

* * *

> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/string/seq-automaton.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/string/seq-automaton.md "edit.link.title")
>  __本页面贡献者：[ouuan](https://github.com/ouuan), [Enter-tainer](https://github.com/Enter-tainer), [Ir1d](https://github.com/Ir1d), [c-forrest](https://github.com/c-forrest), [CCXXXI](https://github.com/CCXXXI), [Chrogeek](https://github.com/Chrogeek), [FFjet](https://github.com/FFjet), [HeRaNO](https://github.com/HeRaNO), [iamtwz](https://github.com/iamtwz), [kenlig](https://github.com/kenlig), [ksyx](https://github.com/ksyx), [ouuan](mailto:1609483441@qq.com), [Tiphereth-A](https://github.com/Tiphereth-A), [ZnPdCo](https://github.com/ZnPdCo)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用