AC自动机

练习题

洛谷 P5357 - AC自动机（二次加强版） (opens new window)

CF1400F - x-prime Substrings (opens new window)

提示一

可以通过DFS枚举出所有的x-prime string。

提示二

利用所有的x-prime string构建AC自动机。

提示三

考虑两种转移：删除当前字母，总花费加一；保留当前字母，在AC自动机上移动。

小贴士

本题中，由于任意一个$x$-prime串都不会是其他$x$-prime串的后缀（否则它们的数位和不等），所以在AC自动机上移动时，并不需要利用fail指针逐级上跳。但务必注意，只有很少的题目能够满足这一条件，不要因此在其他AC自动机的题目上吃到WA（就像我在ADAJOBS那题一样）。

参考代码（C++）

#include <cstring>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;

struct Node {
  int fail = 0, children[9]{};
  bool match = false;
};

string s, t;
int x, dp[5005][5005];
set<string> xprime;
vector<int> suffix = {0};
vector<Node> nodes;

void generate_xprime() {
  if (suffix[0] == x) {
    xprime.insert(t);
    return;
  }
  for (int i = 1; i <= 9 && i + suffix[0] <= x; ++i) {
    t.push_back(i + '0');
    for (int &j : suffix)
      j += i;
    suffix.emplace_back(i);
    bool ok = true;
    for (int &j : suffix)
      if (j != x && x % j == 0) {
        ok = false;
        break;
      }
    if (ok)
      generate_xprime();
    suffix.pop_back();
    for (int &j : suffix)
      j -= i;
    t.pop_back();
  }
}

void build_aca() {
  nodes.emplace_back(Node{});
  for (const string &str : xprime) {
    int curr = 0;
    for (const char &c : str) {
      if (!nodes[curr].children[c - '1']) {
        nodes[curr].children[c - '1'] = nodes.size();
        nodes.emplace_back(Node{});
      }
      curr = nodes[curr].children[c - '1'];
    }
    nodes[curr].match = true;
  }
  queue<int> q;
  for (const int &u : nodes[0].children)
    if (u)
      q.push(u);

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 9; ++i) {
      int &v = nodes[u].children[i];
      if (v) {
        nodes[v].fail = nodes[nodes[u].fail].children[i];
        q.push(v);
      } else
        v = nodes[nodes[u].fail].children[i];
    }
  }
}

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

  // Step 1: Enumerate all x-prime strings
  generate_xprime();

  // Step 2: Build Aho-Corasick automaton with x-prime strings
  build_aca();

  // Step 3: Dynamic programming
  memset(dp, 0x3f, sizeof(dp));
  int n = s.size(), m = nodes.size(), ans = INF;
  dp[0][0] = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      if (dp[i][j] == INF)
        continue;
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
      int nxt = nodes[j].children[s[i] - '1'];
      if (!nodes[nxt].match)
        dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j]);
    }
  for (int j = 0; j < m; ++j)
    ans = min(ans, dp[n][j]);
  cout << ans;
}

SPOJ - Ada and Jobs (opens new window)

本题的难点在于，字符串是动态添加的，但我们不可能在每次查询时都重新构建整个AC自动机。那么应该如何做呢？

提示一

离线所有修改操作和查询，在构建AC自动机时给每个终止节点一个时间戳（代表它是第几个被添加的字符串）；同时，记录每个查询操作发生时字典中总单词数。这样，我们只需要构建一次AC自动机。在每次匹配的过程中，我们需要匹配到时间戳小于等于对应查询操作时间戳的终止节点才算是匹配成功。

提示二

在匹配过程中，并不需要逐级跳fail指针来查找是否存在匹配。可以在构建自动机时顺便将时间戳下推。

参考代码（C++）

#include <iostream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;

struct Node {
  int occur = INF, fail = 0, children[26]{};
};

int main() {
  int q;
  cin >> q;
  vector<string> dict;
  vector<pair<int, string>> query;
  while (q--) {
    int t;
    string s;
    cin >> t >> s;
    if (t == 0)
      dict.emplace_back(s);
    else
      query.emplace_back(dict.size(), s);
  }
  int m = dict.size();
  vector<Node> nodes(1);
  for (int i = 1; i <= m; ++i) {
    int current = 0;
    for (char c : dict[i - 1]) {
      if (!nodes[current].children[c - 'a']) {
        nodes[current].children[c - 'a'] = nodes.size();
        nodes.emplace_back(Node{});
      }
      current = nodes[current].children[c - 'a'];
    }
    nodes[current].occur = min(nodes[current].occur, i);
  }
  queue<int> que;
  for (const int &u : nodes[0].children)
    if (u)
      que.push(u);
  while (!que.empty()) {
    int u = que.front();

    // Push down the timestamp. This is critical.
    nodes[u].occur = min(nodes[u].occur, nodes[nodes[u].fail].occur);
    que.pop();
    for (int i = 0; i < 26; ++i) {
      int &v = nodes[u].children[i];
      if (v) {
        nodes[v].fail = nodes[nodes[u].fail].children[i];
        que.push(v);
      } else
        v = nodes[nodes[u].fail].children[i];
    }
  }
  string ans;
  for (auto &[ts, s] : query) {
    int current = 0;
    bool found = false;
    int idx = 0;
    while (idx < s.size()) {
      char c = s[idx];
      if (nodes[current].children[c - 'a']) {
        current = nodes[current].children[c - 'a'];
        if (nodes[current].occur <= ts) {
          ans += "YES\n";
          found = true;
          break;
        }
        idx++;
      } else {
        current = nodes[current].fail;
        if (!current)
          idx++;
      }
    }
    if (!found)
      ans += "NO\n";
  }
  cout << ans;
}