AIOJ

Before reading this article, read Automata first.

Definition

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

Throughout this article, $s$ denotes that string.

States

If $s$ contains $n$ characters, the sequence automaton has $n+1$ states.

Let $t$ be a subsequence of $s$ . Then $\delta(start, t)$ is the position where $t$ ends at its first occurrence in $s$ .

In other words, state $i$ represents the set difference between the subsequences of the prefix $s[1..i]$ and those of the prefix $s[1..i-1]$ .

Every state of a sequence automaton is an accepting state.

Transitions

The state definition gives $\delta(u, c)=\min\{i|i>u,s[i]=c\}$ , the position of the next occurrence of character $c$ .

Why the “next” occurrence? If $i>j$ , the subsequences of the suffix $s[i..|s|]$ form a subset of those of $s[j..|s|]$ , so choosing the earliest possible occurrence is always optimal.

Implementation

Scan from right to left while maintaining the earliest occurrence 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 takes $O(n|\Sigma|)$ time.

Examples

「HEOI2015」Shortest Non-Common Substring

Given two strings $A$ and $B$ consisting of lowercase English letters ( $1\le |A|, |B|\le 2000$ ), find:

A shortest substring of $A$ that is not a substring of $B$ ;
A shortest substring of $A$ that is not a subsequence of $B$ ;
A shortest subsequence of $A$ that is not a substring of $B$ ;
A shortest subsequence of $A$ that is not a subsequence of $B$ .

Solution

Questions 1 and 3 require a suffix automaton and use similar methods, so only questions 2 and 4 are discussed here.

Question 2 is straightforward: enumerate substrings of $f(i, j)$ , feed them into the sequence automaton of $i$ , and count those that are not accepted.

Question 4 requires DP. Let $j$ be the minimum number of additional characters needed to obtain a non-common subsequence when the sequence automaton of $f(i, \textit{null})=0$ is in state and that of is in state . The transition is

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

The starting condition is .

Reference Code

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

  // Compute the answers for the four cases.
  // 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;
}