Skip to content

Sequence Automaton

Before reading this article, please read Automaton.

Definition

A sequence automaton is an automaton that accepts exactly the subsequences of a given string.

In this article, \(s\) refers to this string.

States

If \(s\) contains \(n\) characters, then the sequence automaton contains \(n+1\) states.

Let \(t\) be a subsequence of \(s\). Then \(\delta(start, t)\) is the position of the end of the first occurrence of \(t\) in \(s\).

That is, a state \(i\) represents the set difference between the subsequences of the prefix \(s[1..i]\) and the subsequences of the prefix \(s[1..i-1]\).

All states in the sequence automaton are accepting states.

Transitions

From the state definition, we have \(\delta(u, c)=\min\{i|i>u,s[i]=c\}\), which is the position of the next occurrence of character \(c\).

Why is it the "next" occurrence? Because if \(i>j\), the set of subsequences of the suffix \(s[i..|s|]\) is a subset of the subsequences of the suffix \(s[j..|s|]\). Thus, choosing the earliest possible occurrence is always optimal.

Implementation

Scan from back to front, maintaining the earliest occurrence position of each character:

\[ \begin{array}{ll} 1 & \textbf{Input. } \text{A string } S\\ 2 & \textbf{Output. } \text{The state transition of the sequence automaton of }S \\ 3 & \textbf{Method. } \\ 4 & \textbf{for }c\in\Sigma\\ 5 & \qquad next[c]\gets null\\ 6 & \textbf{for }i\gets|S|\textbf{ downto }1\\ 7 & \qquad next[S[i]]\gets i\\ 8 & \qquad \textbf{for }c\in\Sigma\\ 9 & \qquad\qquad \delta(i-1,c)\gets next[c]\\ 10 & \textbf{return }\delta \end{array} \]

The construction complexity is \(O(n|\Sigma|)\).

Example Problems

「HEOI2015」Shortest Non-Common Substring

You are given two strings \(A\) and \(B\) consisting of lowercase English letters (\(1\le |A|, |B|\le 2000\)). Find:

  1. The shortest substring of \(A\) that is not a substring of \(B\);
  2. The shortest substring of \(A\) that is not a subsequence of \(B\);
  3. The shortest subsequence of \(A\) that is not a substring of \(B\);
  4. The shortest subsequence of \(A\) that is not a subsequence of \(B\).
Solution

Questions 1 and 3 require suffix automata and have similar solutions. Here we only explain questions 2 and 4.

Question 2 is relatively simple: enumerate substrings of \(A\) and feed them into the sequence automaton of \(B\). If not accepted, count it as an answer.

Question 4 requires DP. Let \(f(i, j)\) denote the number of additional characters needed to form a non-common subsequence when currently at state \(i\) in \(A\)'s sequence automaton and state \(j\) in \(B\)'s sequence automaton. The state transition equation is:

\[ f(i, j)=\min_{\delta_A(i,c)\ne \textit{null}}f(\delta_A(i, c), \delta_B(j, c))+1. \]

The starting point of the transition is \(f(i, \textit{null})=0\).

Reference Code 
  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;  // New node
  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;
  }

  // Calculate answers for four cases
  //  Case 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';

  // Case 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';

  // Case 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';

  // Case 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;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用