跳转至

# 序列自动机

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

## 定义

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

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

### 状态

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

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

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

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

### 转移

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

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

## 实现

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

1 𝐈 𝐧 𝐩 𝐮 𝐭. A s t r i n g 𝑆 2 𝐎 𝐮 𝐭 𝐩 𝐮 𝐭. T h e s t a t e t r a n s i t i o n o f t h e s e q u e n c e a u t o m a t o n o f 𝑆 3 𝐌 𝐞 𝐭 𝐡 𝐨 𝐝. 4 𝐟 𝐨 𝐫 𝑐∈Σ 5 𝑛 𝑒 𝑥 𝑡[𝑐]←𝑛 𝑢 𝑙 𝑙 6 𝐟 𝐨 𝐫 𝑖←|𝑆| 𝐝 𝐨 𝐰 𝐧 𝐭 𝐨 1 7 𝑛 𝑒 𝑥 𝑡[𝑆[𝑖]]←𝑖 8 𝐟 𝐨 𝐫 𝑐∈Σ 9 𝛿(𝑖−1,𝑐)←𝑛 𝑒 𝑥 𝑡[𝑐]1 0 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 𝛿 1 Input. A string S 2 Output. The state transition of the sequence automaton of S 3 Method. 4 for c∈Σ 5 n e x t[c]←n u l l 6 for i←|S| downto 1 7 n e x t[S[i]]←i 8 for c∈Σ 9 δ(i−1,c)←n e x t[c]10 return δ

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

## 例题

「HEOI2015」最短不公共子串

给你两个由小写英文字母组成的串 𝐴 A 和 𝐵 B（1 ≤|𝐴|,|𝐵| ≤2 0 0 0 1≤|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，需要再添加多少个字符能够不是公共子序列．状态转移方程为：

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

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

参考代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19
     20
     21
     22
     23
     24
     25
     26
     27
     28
     29
     30
     31
     32
     33
     34
     35
     36
     37
     38
     39
     40
     41
     42
     43
     44
     45
     46
     47
     48
     49
     50
     51
     52
     53
     54
     55
     56
     57
     58
     59
     60
     61
     62
     63
     64
     65
     66
     67
     68
     69
     70
     71
     72
     73
     74
     75
     76
     77
     78
     79
     80
     81
     82
     83
     84
     85
     86
     87
     88
     89
     90
     91
     92
     93
     94
     95
     96
     97
     98
     99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    #include <algorithm>
    #include <cstring>
    #include <iostream>
    #include <string>
    using namespace std;

    constexpr int N = 2005;

    string s, t;
    int na[N][26], nb[N][26], nxt[26];
    int n, m, a[N], b[N], tot = 1, p = 1, f[N][N << 1];

    struct SAM {
      int par, ch[26], len;
    } sam[N << 1];

    void insert(int x) {
      int np = ++tot;  // 新节点
      sam[np].len = sam[p].len + 1;
      while (p && !sam[p].ch[x]) {
        sam[p].ch[x] = np;
        p = sam[p].par;
      }
      if (p == 0)
        sam[np].par = 1;
      else {
        int q = sam[p].ch[x];
        if (sam[q].len == sam[p].len + 1)
          sam[np].par = q;
        else {
          int nq = ++tot;
          sam[nq].len = sam[p].len + 1;
          memcpy(sam[nq].ch, sam[q].ch, sizeof(sam[q].ch));
          sam[nq].par = sam[q].par;
          sam[q].par = sam[np].par = nq;
          while (p && sam[p].ch[x] == q) {
            sam[p].ch[x] = nq;
            p = sam[p].par;
          }
        }
      }
      p = np;
    }

    int main() {
      cin >> s >> t;

      n = s.size();
      m = t.size();
      s = " " + s;
      t = " " + t;

      for (int i = 1; i <= n; ++i) a[i] = s[i] - 'a';
      for (int i = 1; i <= m; ++i) b[i] = t[i] - 'a';

      for (int i = 1; i <= m; ++i) insert(b[i]);

      // nxt[S[i]]<-i
      for (int i = 0; i < 26; ++i) nxt[i] = n + 1;
      for (int i = n; i >= 0; --i) {
        memcpy(na[i], nxt, sizeof(nxt));
        nxt[a[i]] = i;
      }

      for (int i = 0; i < 26; ++i) nxt[i] = m + 1;
      for (int i = m; i >= 0; --i) {
        memcpy(nb[i], nxt, sizeof(nxt));
        nxt[b[i]] = i;
      }

      // 四种情况计算答案
      //  1
      int ans = N;
      for (int l = 1; l <= n; ++l) {
        for (int r = l, u = 1; r <= n; ++r) {
          u = sam[u].ch[a[r]];
          if (!u) {
            ans = min(ans, r - l + 1);
            break;
          }
        }
      }

      cout << (ans == N ? -1 : ans) << '\n';

      // 2
      ans = N;

      for (int l = 1; l <= n; ++l) {
        for (int r = l, u = 0; r <= n; ++r) {
          u = nb[u][a[r]];
          if (u == m + 1) {
            ans = min(ans, r - l + 1);
            break;
          }
        }
      }

      cout << (ans == N ? -1 : ans) << '\n';

      // 3
      for (int i = n; i >= 0; --i) {
        for (int j = 1; j <= tot; ++j) {
          f[i][j] = N;
          for (int c = 0; c < 26; ++c) {
            int u = na[i][c];
            int v = sam[j].ch[c];
            if (u <= n) f[i][j] = min(f[i][j], f[u][v] + 1);
          }
        }
      }

      cout << (f[0][1] == N ? -1 : f[0][1]) << '\n';

      // 4
      memset(f, 0, sizeof(f));

      for (int i = n; i >= 0; --i) {
        for (int j = 0; j <= m; ++j) {
          f[i][j] = N;
          for (int c = 0; c < 26; ++c) {
            int u = na[i][c];
            int v = nb[j][c];
            if (u <= n) f[i][j] = min(f[i][j], f[u][v] + 1);
          }
        }
      }

      cout << (f[0][0] == N ? -1 : f[0][0]) << '\n';

      return 0;
    }

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：ouuan, Enter-tainer, Ir1d, c-forrest, CCXXXI, Chrogeek, FFjet, HeRaNO, iamtwz, kenlig, ksyx, ouuan, Tiphereth-A, ZnPdCo
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用