17.序列自动机

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

定义

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

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

状态

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

令 $t$ 是 $s$ 的一个子序列，那么 $\delta (start,t)$ 是 $t$ 在 $s$ 中第一次出现时末端的位置。

也就是说，一个状态 $i$ 表示前缀 $s[\mathrm{1..}i]$ 的子序列与前缀 $s[\mathrm{1..}i-1]$ 的子序列的差集。

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

转移

由状态定义可以得到，$\delta (u,c)=\min \{i|i>u,s[i]=c\}$，也就是字符 $c$ 下一次出现的位置。

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

实现

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

这样构建的复杂度是 $O(n|\Sigma |)$。

例题

「HEOI2015」最短不公共子串

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

$$f(i,j)=\underset{{\delta }_A(i,c)\ne \text{null}}{\min }f({\delta }_A(i,c),{\delta }_B(j,c))+1.$$

转移起点为 $f(i,\text{null})=0$。

参考代码

#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;
}