笔记汇总

$AC$ 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的。

它最大的特点是在确保正确的情况下最快。

简单来说，建立一个 AC 自动机有两个步骤：

1. 基础的 Trie 结构：将所有的模式串构成一棵 Trie。
2. KMP 的思想：对 Trie 树上所有的结点构造失配指针。

然后就可以利用它进行 多模式串匹配 了。

失配指针

与$next$串的对比：

1. 共同点：两者同样是在失配的时候用于跳转的指针。
2. 不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

即在失配后跳到其它分支上的与其真后缀相等的最长真前缀的末尾上。

或者说在不同模式串上的部分匹配表。

实现

建字典树

void insert(char *s) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot;  // 如果没有则插入新节点
    u = tr[u][s[i] - 'a'];                              // 搜索下一个节点
  }
  e[u]++;  // 尾为节点 u 的串的个数
}

建失配指针

tr[u][c] 从u往后加一个字符c到达的结点

void build() {
  for (int i = 0; i < 26; i++)
    if (tr[0][i]) q.push(tr[0][i]); 
  while (q.size()) {    // bfs 更新确保前面阶段求出
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u][i])
        fail[tr[u][i]] = tr[fail[u]][i];
        // tr[u][i] 的失配指针等于其父节点的失配指针下沿（若有的话）的节点编号
        q.push(tr[u][i]);
      else
        tr[u][i] = tr[fail[u]][i];
        // 没有时快速返回，减少时间复杂度
    }
  }
}

多模式匹配

int query(char *t) {    // 搜索模式串的字符数组
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {  // 非空搜索
    u = tr[u][t[i] - 'a'];      // 往后走
    for (int j = u; j && e[j] != -1; j = fail[j]) { // 未走完且未重复走则统计出现过的模式串数量
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

由于 $e$ 同时需要记录是否重复，所以我们在多次搜索时会新增一个 $copy$ 数组。

扩展

T1

输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

查询路径有单向路径搜索算法，时间复杂度 $O(n)$。

但字符串是连续的，所以用 $hash$ 也可以，时间复杂度 $O(1)$。

对比:

int query(char *t) {    // 搜索模式串的字符数组
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {  // 非空搜索
    u = tr[u][t[i] - 'a'];      // 往后走
    for (int j = u; j && e[j] != -1; j = fail[j]) { // 未走完且未重复走则统计出现过的模式串数量
      res += e[j], e[j] = -1;
    }
  }
  return res;
}

// 以 u 为结尾的字符串编号为 idx[u]

int query(char *t) {  // 返回最大的出现次数
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u][t[i] - 'a'];
    for (int j = u; j; j = fail[j]) val[j]++;
    // 可以重复走，不用 e 数组
  }
  for (int i = 0; i <= tot; i++)    // 搜索所有节点, 但只用看字符串的末尾结点（的编号）
    if (idx[i]) res = max(res, val[i]), cnt[idx[i]] = val[i]; // 最优化更新, 维护 cnt 以便于输出出现次数相同的字符串
  return res;   // 出现次数
}