Trie + KMP的结合体 AC自动机 -> Trie图

将next数组搬到trie里，每个节点的next值指以当前节点为终点的和以根节点为起点的非平凡(不能从根节点到当前节点的子串)的最长公共前后缀的长度。
KMP本质就是AC自动机在一条链上的情况。

0x00 求next

bfs求解next，将KMP求next的过程类比到trie上

  1. // 优化前
  2. // 求next
  3. static void build() {
  4.     int hh = 0, tt = -1;
  5.     for (int i = 0; i < 26; i++) {
  6.         if (tr[0][i] != 0)
  7.             q[++tt] = tr[0][i];
  8.     }
  10.     while (hh <= tt) {
  11.         int u = q[hh++];
  12.         for (int i = 0; i < 26; i++) {
  13.             int c = tr[u][i];
  14.             if (c == 0) continue;
  15.             int j = ne[u];
  16.             while (j > 0 && tr[j][i] == 0)
  17.                 j = ne[j];
  18.             if (tr[j][i] != 0)
  19.                 j = tr[j][i];
  20.             ne[c] = j;
  21.             q[++tt] = c;
  22.         }
  23.     }
  24. }

Trie图

  1. // 优化后
  2. static void build() {
  3.     int hh = 0, tt = -1;
  4.     for (int i = 0; i < 26; i++) {
  5.         if (tr[0][i] != 0)
  6.             q[++tt] = tr[0][i];
  7.     }
  9.     while (hh <= tt) {
  10.         int u = q[hh++];
  11.         for (int i = 0; i < 26; i++) {
  12.             int c = tr[u][i];
  13.             if (c == 0) {
  14.                 tr[u][i] = tr[ne[u]][i];    // 一步到位
  15.             } else {
  16.                 ne[c] = tr[ne[u]][i];
  17.                 q[++tt] = c;
  18.             }
  19.         }
  20.     }
  21. }

优化后，tr[u][i]直接指向首个匹配，若没有匹配，指向0。省掉了一维while

0x01 匹配

  1. // 优化前的匹配
  2. String s = sc.next();
  3. int res = 0;
  4. for (int i = 0, j = 0; i < s.length(); i++) {
  5.     int id = s.charAt(i) - 'a';
  6.     while (j > 0 && tr[j][id] == 0)
  7.         j = ne[j];
  8.     if (tr[j][id] != 0)
  9.         j = tr[j][id];
  10.     int p = j;
  11.     while (p > 0) {
  12.         res += cnt[p];
  13.         cnt[p] = 0;
  14.         p = ne[p];
  15.     }
  16. }

Trie图

  1. // 优化后的匹配
  2. String s = sc.next();
  3. int res = 0;
  4. for (int i = 0, j = 0; i < s.length(); i++) {
  5.     int id = s.charAt(i) - 'a';
  6.     j = tr[j][id];
  8.     int p = j;
  9.     while (p > 0) {
  10.         res += cnt[p];
  11.         cnt[p] = 0;
  12.         p = ne[p];
  13.     }
  14. }

0x03 应用

AcWing 1053. 修复DNA
AC自动机 + 状态机DP
思路：
状态表示：f[i][j]表示考虑文本串的前i个字符，当前走到了AC自动机的位置j的所有操作方案中最少的字符修改数量。

AcWing 1285. 单词
AC自动机 + 拓扑DP

目的：求每个字符串出现的次数
一个字符串出现的次数= 所有满足要求的前缀个数（要求是前缀的后缀包含该字符串）
考虑每个前缀字符串的后缀可以等于哪些目标字符串。正好符合next数组的定义，通过递归就能统计到所有的目标串。
递归的方法就是按照拓扑序的倒序，因为Trie图本身是有向无环图