《数据结构与算法之美》基础篇笔记（五）

2021-02-11

摘要：极客时间《数据结构与算法之美》基础篇笔记，图、深度和广度优先搜索、BM 算法、RK 算法、BM 算法、KMP 算法、AC 自动机算法

图 Graph

图是一种比树更复杂的非线性表结构。图中的元素称为顶点（vertex），每个顶点可以与任意其他顶点建立关系，这种关系叫做边（edge），每个顶点边的条数叫做顶点的度（degree）。如果边有方向叫做“有向图”，没有方向的称为“无向图”。在有向图中，度可以分为出度和入度，顶点的入度表示有多少边指向该顶点，出度表示有多少边是以这个顶点为起点指向其他顶点。还有带权图（weighted graph），每条边都有一个权重（weight）。

存储图

图最直观的存储方法是邻接矩阵，邻接矩阵底层依赖的是二维数组。无向图中，如果顶点 i 到顶点 j 之间有边， A[i][j] 和 A[j][i] 会标记为 1；有向图中，如果顶点 i 有一条指向顶点 j 的边，A[i][j] 就标记为 1；如果是带权图，数组中就存储相应的权重。

邻接矩阵的存储是基于数组，因而在获取两个顶点的关系时非常高效，而且计算时可以将很多图的运算转化成矩阵之间的计算。但是邻接矩阵很浪费浪费空间，比如无向图，只需要一个边即可表示两者关系。稀疏图的顶点很多，但每个顶点的关系不多就更加浪费空间。
还有另外一种存储方法是邻接表，邻接表类似散列表，每个顶点对应一条链表，链表存储的是与该顶点相连接的其他顶点

邻接表存储起来比较节省空间，但是查询关系时要遍历链表比较耗时。为了提高效率，可以将其类比散列表进行优化，比如将链表改为其他高效率查询的数据结构跳表、红黑树、散列表、动态有序数组（二分法查找）等。
以微博为例，需要支持几项功能：1、判断用户 A 是否关注了用户 B；2、判断用户 A 是否是用户 B 的粉丝；3、关注与取消关注的功能；4、根据用户姓名首字母排序，分页展示粉丝和关注列表。相比于用户之间的关系，用户数量明显更多，使用邻接表存储。一个邻接表存储的是出表度，还需要一个逆邻接表存储入表度。将邻接表中的链表改为跳表更为合适，因为跳表的数据本身就是有序的，这样分页获取粉丝列表或者关注列表更高效。如果数据量非常大，可以通过哈希算法先将数据分片，不同的机器存储不同用户顶点的邻接表和逆邻接表。当要查询不同顶点之间关系时，先使用哈希算法计算得到对应顶点数据所在机器，然后在目标机器上查询信息。

广度优先搜索（BFS）

广度优先搜索先查找距离顶点最近的，依次往外搜索，通常借助队列实现，遍历本级数据时将下一级顶点依次存储到队列中。广度优先搜索查询出的路径是最短路径

// java 广度优先搜索
public void bfs(int s, int t) {
  if (s == t) return;
  boolean[] visited = new boolean[v];
  visited[s]=true;
  Queue<Integer> queue = new LinkedList<>();
  queue.add(s); // 起始顶点入队
  int[] prev = new int[v];
  for (int i = 0; i < v; ++i) { // 遍历添加默认值 -1
    prev[i] = -1;
  }
  while (queue.size() != 0) {
    int w = queue.poll(); // 取出队首顶点
    for (int i = 0; i < adj[w].size(); ++i) { // 遍历顶点的边
      int q = adj[w].get(i); // 拿到边对应的目标顶点
      if (!visited[q]) {  // 目标顶点没有访问过
        prev[q] = w; // 保存目标顶点与前驱顶点的连接关系
        if (q == t) { // 如果目标顶点与终止顶点相等则打印退出程序
          print(prev, s, t);
          return;
        }
        visited[q] = true; // 标记目标顶点已访问过
        queue.add(q); // 目标顶点入队
      }
    }
  }
}

private void print(int[] prev, int s, int t) { // 递归打印s->t的路径
  if (prev[t] != -1 && t != s) {
    print(prev, s, prev[t]);
  }
  System.out.print(t + " ");
}

这里有三个辅助变量：
visited 是用来记录已经被访问的顶点，访问过的顶点对应值会被标记为 true，防止重复访问
queue 是一个队列，用来存储下一层顶点
prev 用来记录搜索路径，保存的是指向顶点的前驱顶点
在最坏情况下，顶点 s 需要遍历整个图才能找到 s。此时，所有的顶点和边都会被访问一次，广度优先搜索的时间复杂度是 O(V+E) ，E 是边的个数，V 是顶点个数。如果是连通图（每个顶点之间有路径可直接或间接的相连）有 E>=V-1 ，所以广度优先搜索的时间复杂度也可以简写为 O(E)。广度优先搜索的空间消耗主要在三个辅助变量上，而这三个变量的大小都不会超多顶点个数，所以空间复杂度是 O(V)。

深度优先搜索（DFS）

深度优先搜索用的是回溯思想，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。通常借助栈来实现

// java 深度优先搜索
boolean found = false; // 全局变量或者类成员变量

public void dfs(int s, int t) {
  found = false;
  boolean[] visited = new boolean[v];
  int[] prev = new int[v];
  for (int i = 0; i < v; ++i) {
    prev[i] = -1;
  }
  recurDfs(s, t, visited, prev);
  print(prev, s, t);
}

private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
  if (found == true) return; // 如果 found 为 true，说明已经查到对应顶点，那么 for 循环后面的递归函数都要跳出
  visited[w] = true;
  if (w == t) {
    found = true;
    return;
  }
  for (int i = 0; i < adj[w].size(); ++i) {
    int q = adj[w].get(i);
    if (!visited[q]) {
      prev[q] = w;
      recurDfs(q, t, visited, prev);
    }
  }
}

深度优先搜索算法的每条边最多被访问两次：一次是遍历，另一次是回退，所以深度优先搜索算法的时间复杂度为 O(E)，E 为边的个数。深度优先算法消耗的内存主要是 visited、prev 和递归调用栈，visited 和 prev 都与 V 成正比，而递归调用栈也不会超过顶点的数量 V，所以空间复杂度为 O(V)。即在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)。

字符串匹配

字符串匹配中，在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。
单模式串匹配算法：是在一个模式串和一个主串之间进行匹配，即在一个主串中查找一个模式串，有BM 算法、RK 算法、BM 算法。
多模式串匹配算法：就是在多个模式串和一个主串之间做匹配，即在一个主串中查找多个模式串，有 KMP 算法、Trie树。

BF 算法

BF（Brute Force）算法中文叫作暴力匹配算法，也叫朴素匹配算法。BF 算法简单粗暴，但性能不高。BF 算法的思想：在主串中，检查起始位置分别是 0、1、2….n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的，当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。
使用 BF 算法匹配字符串的最坏时间复杂度为O(n*m)，但有两点原因使其比较常用：1、实际开发中，主串和模式串的长度都不会很大；2、算法的思想简单，代码实现也简单而不易出错

RK 算法

RK 算法的全称叫 Rabin-Karp 算法。RK 算法的思路：通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小，如果两者相等，说明对应的子串与模式串相等。因为哈希值是一个数字，数字的匹配要比普通字符串匹配高效。但有一点：使用了哈希函数，算法的整体过程不一定比原来高效。这就要求必须提高哈希算法计算子串哈希值的效率：假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。这样做有两点优势：1、相邻的两个子串有关联，计算出一个子串哈希值可以快速计算出相邻子串的哈希值；2、进制转换时，我们可以提前将次方值计算好存储在一个数组中，通过查表快速得到结果。
如果字符串中只包含 a～z 这 26 个小写字符，我们用二十六进制 025 来表示一个字符串，对应的哈希值就是二十六进制数转化成十进制的结果。假设主串 S 长度为 n，下标从 0 开始，模式串长度为 m。下标从 i-1 开始的子串哈希值为h[i-1]=26^(m-1)(S[i-1]-'a')+26^(m-2)(S[i]-'a')+...+26^0(S[i+m-2]-'a')，下标从 i 开始的子串哈希值为26^(m-1)(S[i]-'a')+...+26^1(S[i+m-2]-'a')+26^0(S[i+m-1]-'a')，可以看出前者除去第一项，后者除去第二项，剩下的后者是前者的 26 倍，则两者哈希值的关系h[i]=(h[i-1]-26^(m-1)(S[i-1]-'a'))*26+(S[i+m-1]-'a')。再将 26 的 0m-1 次方先存储到一个数组中，0~m-1 即为对应次方的索引[26^0,26^1,26^2,...,26^(m-1)]。
整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。计算子串哈希值时，得到第一个子串的哈希值后，可以快捷计算出相邻的子串哈希值，只要遍历一遍主串即可得到所有子串的哈希值，其时间复杂度为 O(n)。子串哈希值共有 n-m+1 个要与模式串哈希值作比较，时间复杂度也为 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)，要比 BF 算法高效。哈希算法的冲突概率要相对控制得低一些，一般情况下冲突不会很多，如果有冲突就将子串与模式串本身相比较好了。极端情况下，哈希算法大量冲突，时间复杂度就退化为 O(n*m)。

BM 算法

BM 算法全称 Boyer-Moore，其核心思想：当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。

坏字符规则

BF 算法和 RK 算法在匹配过程中，我们都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。而 BM 算法则是按照模式串下标从大到小的顺序，倒着与主串中的字符进行匹配的。从模式串的末尾往前倒着匹配，当某个字符没法匹配的时候，这个主串中的字符就叫做坏字符。当发生不匹配的时候，把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作 xi。如果不存在，xi 记作 -1。那模式串往后移动的位数就等于 si-xi。如果坏字符在模式串里多处出现，那么 xi 为最后那一个的下标。si-xi 有可能为负数，此时还需要利用好后缀规则：分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数

好后缀规则

模式串倒着与主串中的字符进行匹配时，已经匹配的字符串叫作好后缀，记作 {u}。如果模式串中找到与 {u} 相匹配的字符串 {u*}，直接将两者对齐即可。如果模式串中没有与 {u} 相匹配的字符串，则从好后缀的后缀子串中，找一个最长且能与模式串的前缀子串相匹配的字符串记作 {v}，将两者对齐。
模式串中未匹配好后缀

实现

代码也是按照坏字符规则和好后缀规则配合其他技巧来实现。首先实现坏字符规则，找到坏字符后得到 si，然后在模式串中得到 xi，最后计算 si-xi 的值。获取 xi 时有一个技巧：如果拿坏字符直接在模式串中顺序遍历查找，比较低效，而使用散列表会更高效。散列表简单实现：假设字符串的字符集不是很大，每个字符长度是 1，我们使用 256 长度的数组来记录每个字符在模式串中最后出现的位置（索引）。这个数组中，元素下标对应字符的 ASCII 码值，元素对应字符在字符串中的位置
坏字符技巧

private static final int SIZE = 256; // 全局变量或成员变量
private void generateBC(char[] b, int m, int[] bc) {
  for (int i = 0; i < SIZE; ++i) {
    bc[i] = -1; // 初始化 bc 赋值 -1
  }
  for (int i = 0; i < m; ++i) {
    int ascii = (int)b[i]; // 计算 b[i] 的 ASCII 值
    bc[ascii] = i; // 更新字符出现的位置，遍历一遍后即得到模式串中所有字符最后所在的位置，不包含的字符对应的元素值仍为 -1
  }
}

之后按照坏字符规则实现得到 si 与 xi 的逻辑，暂时忽略差值为负数的情况，后面假如好后缀代码后取两者之中的大数即可

// a、b 表示主串和模式串；n、m 表示主串和模式串的长度
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
  generateBC(b, m, bc); // 构建坏字符哈希表
  int i = 0; // i 表示主串与模式串对齐的第一个字符
  while (i <= n - m) { 
    int j; // 模式串当前匹配字符下标索引
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 查找坏字符对应模式串中的下标 si 即 j
    }
    if (j < 0) { // 说明模式串与主串的当前子串完全匹配
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    // 模式串与主串的当前子串不相同，查找坏字符 a[i+j] 在散列表 bc 中的下标 xi，然后计算 si-xi 即 j-bc[(int)a[i+j]] 得到向后移动的位数
    i = i + (j - bc[(int)a[i+j]]); 
  }
  return -1;
}

然后实现好后缀规则，每次匹配都要用好后缀与模式串进行匹配以判断移动位置，同样很低效。我们可以预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。
巧妙方法：
1、模式串的后缀子串都是确定的，其长度也是确定的，只要记录子串长度即可确定对应的后缀子串
2、引入 suffix 数组，下标表示后缀子串的长度，元素存储的是模式串中 0~m-2 的子串与好后缀 {u} 相匹配的另一个子串 {u*} 的起始下标值，如果 {u*} 不止一个，则记录最大的下标
3、引入 prefix 数组，下标表示后缀子串的长度，记录模式串的后缀子串是否能匹配模式串的前缀子串
suffix 与 prefix 填充方法：两个数组的下标都为后缀子串的长度，拿下标从 0 到 i 长度为 k 的子串（i 可以是 0 到 m-2），与整个模式串求公共后缀子串，并记录起始下标值 suffix[k] 即得到 suffix 数组。如果下标为 0，说明公共后缀子串同时也是前缀子串，则 prefix[k] 为 true。例如：
好后缀技巧

// b 表示模式串，m 表示长度，suffix，prefix 数组事先申请好
private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
  for (int i = 0; i < m; ++i) { // 初始化
    suffix[i] = -1;
    prefix[i] = false;
  }
  for (int i = 0; i < m - 1; ++i) { // 前缀子串范围是 b[0, i]
    int j = i;
    int k = 0; // 公共后缀子串长度
    while (j >= 0 && b[j] == b[m-1-k]) { // 前缀子串与模式串求公共后缀子串
      --j;
      ++k;
      suffix[k] = j+1; // j+1 表示公共后缀子串在模式串b[0, i]中的起始下标
    }
    if (j == -1) prefix[k] = true; // 如果公共后缀子串也是模式串的前缀子串
  }
}

将好后缀规则代码逻辑加到

// a、b 表示主串和模式串；n、m 表示主串和模式串的长度
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
  generateBC(b, m, bc); // 构建坏字符哈希表
  int[] suffix = new int[m];
  boolean[] prefix = new boolean[m];
  generateGS(b, m, suffix, prefix); // 构建 suffix 与 prefix
  int i = 0; // i 表示主串与模式串对齐的第一个字符
  while (i <= n - m) {
    int j; // 模式串当前匹配字符下标索引
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 查找坏字符对应模式串中的下标 si 即 j
    }
    if (j < 0) { // 说明模式串与主串的当前子串完全匹配
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    // 模式串与主串的当前子串不相同，查找坏字符 a[i+j] 在散列表 bc 中的下标 xi，然后计算 si-xi 即 j-bc[(int)a[i+j]] 得到向后移动的位数
    int x = j - bc[(int)a[i+j]];
    int y = 0; // 
    if (j < m-1) { // 坏字符下标小于模式串最后一位字符索引，说明有好后缀
      y = moveByGS(j, m, suffix, prefix); // 获取需要移动的位数
    }
    i = i + Math.max(x, y);
  }
  return -1;
}

// j 表示坏字符对应的模式串中的字符下标; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
  int k = m - 1 - j; // 好后缀长度
  if (suffix[k] != -1) return j+1-suffix[k]; // 不等于 -1，说明存在 {u*}，其起始索引为 suffix[k]，将 {u*} 移动到索引 j 后面与 {u} 对齐，即从 suffix[k] 到 j+1 ，需要移动 j+1-suffix[k] 位
  for (int r = j+2; r <= m-1; ++r) { // 如果没有 {u*}，则寻找好后缀的后缀子串与前缀子串的最长公共子串 {v}，好后缀下标范围 [j+1,m-1]，则好后缀的后缀子串下标范围是 [j+2,m-1]
    if (prefix[m-r] == true) { // 好后缀的后缀子串同时也是模式串的前缀子串 {v}，需要将前缀子串与后缀子串对齐，{v} 长度为 m-r，需要移动 m-(m-r)=r 位
      return r;
    }
  }
  return m; // 如果都没有就移动整个模式串的长度
}

好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，整个算法用到了额外的 3 个数组，bc 数组的大小跟字符集大小有关，suffix 数组和 prefix 数组的大小跟模式串长度 m 有关。为了节省内存，我们可以只用好后缀规则来实现 BM 算法，防止字符集很大造成 bc 数组对内存的过度消耗。

KMP 算法

KMP 算法全称 Knuth Morris Pratt 算法，它的核心算法与 BM 算法非常相近，都是当遇到不可匹配的字符时想要模式串多向后滑动几位，但 KMP 算法是按模式串下标从小到大的顺序匹配。在模式串和主串匹配的过程中，把不能匹配的那个字符仍叫作坏字符，把已经匹配的那段字符串叫作好前缀。我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。假设最长可匹配前缀子串 {v}，长度是 k。每次遇到下标为 j 的坏字符时，我们就把模式串一次性往后滑动 j-k 位，将 j 更新为 k，i 不变，然后继续比较。
KMP原理
实际上，最长可匹配的前缀和后缀子串与主串无关，只与模式串自身有关。因此可以预先处理计算好这些数据，等到匹配时直接使用。KMP 算法提前构建一个数组，数组的下标是每个前缀结尾字符下标（子串长度减 1），值为模式串每个前缀的最长可匹配前缀子串的结尾字符下标，这个数组定义为 next 数组或失效函数（failure function）
KMP失效数组

// a、b 分别是主串和模式串；n、m 分别是主串和模式串的长度
public static int kmp(char[] a, int n, char[] b, int m) {
  int[] next = getNexts(b, m); // 构建失效函数
  int j = 0; // 记录坏字符在模式串的下标，也是最长可匹配前缀子串的长度
  for (int i = 0; i < n; ++i) { // 按下标从小到大的顺序开始匹配
    while (j > 0 && a[i] != b[j]) { // 查找坏字符
      j = next[j - 1] + 1; // i 不变，更新 j ，直到没有可匹配的前缀子串 j=0 或有前缀子串 a[i] = b[j])
    }
    if (a[i] == b[j]) { // 判断模式串对应更新后下标的值是否与主串匹配
      ++j;
    }
    if (j == m) { // 找到匹配模式串的了
      return i - m + 1;
    }
  }
  return -1;
}

// b 表示模式串，m 表示模式串的长度
private static int[] getNexts(char[] b, int m) {
  int[] next = new int[m];
  next[0] = -1; // 失效函数第一位默认没有最长可匹配前缀
  int k = -1; // 记录最长可匹配前缀的最后一位字符的下标
  for (int i = 1; i < m; ++i) { // 从第 2 个字符开始
    while (k != -1 && b[k + 1] != b[i]) { // 不断获取最长可匹配前缀子串的最长可匹配前缀子串，直到最长可匹配前缀子串的下一位与 b[i] 相等或没有最长可匹配前缀子串
      k = next[k];
    }
    if (b[k + 1] == b[i]) { // 最长可匹配前缀子串的下一位元素与 b[i] 相等，那么 k+1 就是 b[0,i] 的最长可匹配前缀子串最后一位字符的下标
      ++k;
    }
    next[i] = k;
  }
  return next;
}

重点理解失效函数，这里使用了一个技巧：我们计算 next[i] 时，用到了之前已经得到的 next[0]~next[i-1]。
假设 next[i-1]=k-1，那么 b[0,k-1] 是 b[0,i-1] 的最长可匹配后缀子串；如果 b[k] 也等于 b[i]，那么 b[0,k] 也是 b[0,i] 的最长可匹配后缀子串。
如果 b[k] 不等于 b[i]，那么 b[0,k-1] 仍是 b[0,i] 可匹配后缀子串，但不一定是最长可匹配后缀子串。此时，查找 b[0,i-1] 的次长可匹配后缀子串 b[x,i-1]，如果次长后缀子串 b[x,i-1] 对应的可匹配前缀子串 b[0,i-1-x] 的下一个字符 b[i-x] 等于 b[i]，那么 b[x,i] 就是 b[0,i] 的最长可匹配后缀子串。如此，问题变成如何查找 b[0,i-1] 的次长可匹配后缀子串。次长可匹配后缀子串在最长可匹配后缀子串中对应后几位 b[y,i-1-y]，在最长可匹配前缀子串 b[0,y] 中对应的是前几位。而最长可匹配后缀子串 b[y,i-1-y] 又等于最长可匹配前缀子串 b[0,y]，这相当于求最长可匹配前缀子串 b[0,y] 的最长可匹配前缀子串 b[0,next[y]]。然后不断循环 b[next[y]+1] 等于不等于 b[i] 这个判断逻辑。
总结这两种情况：
1、如果 b[i-1] 的最长前缀的下一个字符与 b[i] 相等，则 next[i]=next[i-1]+1；
2、如果 b[i-1] 的最长前缀的下一个字符与 b[i] 不相等，则找到 b[0,i-1] 的最长可匹配前缀子串 b[0,next[i-1]] 的最长可匹配前缀子串 b[0,next[next[i-1]]]，此时再将字符 b[0,next[next[i-1]]] 与 b[i] 相比较，不断循环判断后得到 next[i]

KMP 算法复杂度

KMP 算法只有一个额外的 next 数组，与模式串的长度 m 有关，其空间复杂度为 O(m)
KMP 算法分两部分：构建 next 数组和借助 next 数组匹配。构建 next 数组时有两个循环：一个 for 循环，其时间复杂度为 O(m)；另一个是 while 循环，循环中 k=next[k] 使 k 值不断减小，k=next[k] 总的执行次数也不可能超过 m。因此，第一部分时间复杂度为 O(m)。第二部分与第一部分的情况类似 while 循环次数不会超过主串长度 n，时间复杂度为 O(n)。综合起来，KMP 算法的时间复杂度为 O(m+n)

Trie 树

Trie 树，也叫字典树。它是一个树形结构，用来解决在一组字符串集合中快速查找某个字符串的问题。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。树的每个节点表示一个字符串中的字符，但根节点不包含任何信息。
Trie 树主要有两个操作：
1、将字符串集合构造成 Trie 树
2、在 Trie 树中查询一个字符串

// java
public class Trie {
  private TrieNode root = new TrieNode('/'); // 存储无意义字符

  // 往 Trie 树中插入一个字符串
  public void insert(char[] text) {
    TrieNode p = root;
    for (int i = 0; i < text.length; ++i) {
      int index = text[i] - 'a';
      if (p.children[index] == null) { // 如果指针为 null，创建新节点并建立关系
        TrieNode newNode = new TrieNode(text[i]);
        p.children[index] = newNode;
      }
      p = p.children[index]; // 目标节点换为对应子节点
    }
    p.isEndingChar = true; // 字符串最后一个字符标识
  }

  // 在 Trie 树中查找一个字符串
  public boolean find(char[] pattern) {
    TrieNode p = root;
    for (int i = 0; i < pattern.length; ++i) {
      int index = pattern[i] - 'a'; // 通过字符的 ASCII 码减去“a”的 ASCII 码，迅速找到匹配的子节点的指针
      if (p.children[index] == null) {
        return false; // 不存在pattern
      }
      p = p.children[index];
    }
    return p.isEndingChar; // 判断是否为最后一个字符标识来分辨有无该字符串
  }

  // 节点辅助类
  public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26]; // 假设字符串中只有从 a 到 z 这 26 个小写字母，元素不存在时为 null
    public boolean isEndingChar = false; // 是否为字符串最后一个字符的标识
    public TrieNode(char data) {
      this.data = data;
    }
  }
}

// js
// 节点辅助类
class TrieNode {
  constructor(data) {
    this.data = data;
    this.children = new Array(26);
    this.isEndingChar = false // 结尾字符标识
  }
}
// Trie 树类
class TrieTree {
  constructor() {
    this.root = new TrieNode('/')
  }

  // 插入一个字符串
  insert(string) {
    let node = this.root;
    for (let char of string) {
      let index = char.charCodeAt() - 'a'.charCodeAt();
      if (!node.children[index]) {
        node.children[index] = new TrieNode(char);
      }
      node = node.children[index];
    }
    node.isEndingChar = true;
  }

  // 查找一个字符串
  find(string) {
    let node = this.root;
    for (let char of string) {
      let index = char.charCodeAt() - 'a'.charCodeAt();
      if (!node.children[index]) {
          return false;
      }
      node = node.children[index];
    }
    return node.isEndingChar;
  }
}

构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。Trie 树构建完成后，查询字符串十分高效。因为跟原本那组字符串的长度和个数没有任何关系，只跟目标字符串的长度有关系。查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度

Trie 树优缺点

Trie 树是非常耗内存的，用的是一种空间换时间的思路。因为每个节点都要存储一个长度为 26 的数组，如果还有其他字符，这个数组会更长。为了提高内存使用率，可以将数组改为有序数组、跳表、散列表、红黑树等，但这样做又会因为要维护数据有序性降低字符串的插入和查询效率。
Trie 树比较适合的是查找前缀匹配的字符串，如搜索引擎中的关键词提示功能这个场景。
它受多个因素限制：
1、字符串中包含的字符集不能太大，否则会很浪费空间。即便是优化，也要降低其插入和查询的效率
2、要求字符串的前缀重合比较多，不然空间消耗会变大很多
3、自己实现 Trie 树就很麻烦
4、Trie 树中用到了指针，通过指针串起来的数据块是不连续的，对 cpu 缓存来说不友好

AC 自动机算法

AC 自动机算法，全称是 Aho-Corasick 算法。AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，不过此处的 next 数组是构建在树上
AC 自动机的构建，包含两个操作：
1、将多个模式串构建成 Trie 树；
2、在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）
Trie 树中的每一个节点都有一个失败指针，它的作用和构建过程，跟 KMP 算法中的 next 数组极其相似。从根节点到当前节点所组成的字符串的后缀子串与其他模式串匹配，如果某个后缀子串可以匹配某个模式串的前缀，这个后缀子串叫作可匹配后缀子串，而节点的失败指针指向那个最长匹配后缀子串对应的模式串的前缀的最后一个节点。
AC 自动机失败指针
如上图，构成 Trie 树的模式串有：abcd、bcd、c，其中根节点到紫色节点 c 的字符串 abc 的后缀子串有 bc、c，与其他模式串的前缀子串相匹配后，其失败指针指向最长的前缀 bc 的最后一个节点 c 上。
如果把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层。要求某个节点的失败指针的时候，可以像 KMP 算法那样，通过已经求得的、深度更小的那些节点的失败指针来推导。失败指针的构建过程，是一个按层遍历树的过程。
首先 root 的失败指针为 NULL，也就是指向自己。假设节点 p 的失败指针指向节点 q，看节点 p 的子节点 pc 对应的字符与 q 的子节点中有没有与 pc 相同的 qc 节点。如果有的话，就将节点 pc 的失败指针指向节点 qc。如果没有，q=q->fail(失败指针)，即将目标节点 q 换为 q 的失败指针所指向的节点，不断的判断，直到 q 为根节点 root，将其失败指针指向 root

public void buildFailurePointer() {
  Queue<AcNode> queue = new LinkedList<>(); // 链式队列
  root.fail = null; // 根节点的失败指针指向 null
  queue.add(root); // 队列添加根节点
  while (!queue.isEmpty()) {
    AcNode p = queue.remove(); // 取出队列第一个元素
    for (int i = 0; i < 26; ++i) { // 依次设置子节点的失败指针
      AcNode pc = p.children[i];
      if (pc == null) continue; // 跳过空值
      if (p == root) { // 下一层是根节点时，失败指针指向 root
        pc.fail = root;
      } else {
        AcNode q = p.fail;
        while (q != null) { // 递归遍历节点的失败指针
          AcNode qc = q.children[pc.data - 'a']; // 获取对应位置上的子节点 qc
          if (qc != null) { // 有值将 pc 的失败指针指向 qc
            pc.fail = qc;
            break;
          }
          q = q.fail; // 没有则将目标节点换为 q 的失败指针所指向的节点
        }
        if (q == null) { // 遍历完都没有找到，则将失败指针指向根节点
          pc.fail = root;
        }
      }
      queue.add(pc); // 将子节点加入队列，以便获取下一层节点的失败指针
    }
  }
}

使用模式串构建完 AC 自动机后，应用其来匹配主串

public void match(char[] text) { // text 是主串
  int n = text.length;
  AcNode p = root;
  for (int i = 0; i < n; ++i) {
    int idx = text[i] - 'a'; // 得到子节点索引
    while (p.children[idx] == null && p != root) { // 使用失败指针不断更新目标元素，while 2
      p = p.fail; // 失败指针发挥作用的地方
    }
    p = p.children[idx];
    if (p == null) p = root; // 如果没有匹配的，从 root 开始重新匹配
    AcNode tmp = p;
    while (tmp != root) { // 打印出可以匹配的模式串 while 2
      if (tmp.isEndingChar == true) {
        int pos = i-tmp.length+1;
        System.out.println("匹配起始下标" + pos + "; 长度" + tmp.length);
      }
      tmp = tmp.fail; // 不断更新目标元素，以便打印出所有匹配的字符串
    }
  }
}

在匹配过程中，主串从 i=0 开始，AC 自动机从指针 p=root 开始。代码中两个 while 循环逻辑：
1、如果 p 指向的节点有一个等于 AC 自动机的子节点 x，我们就更新 p 指向 x，这个时候我们需要通过失败指针，检测一系列失败指针为结尾的路径是否是模式串。之后我们将 i 加 1，继续这 2 个过程；
2、如果 p 指向的节点没有等于 AC 自动机的子节点，那失败指针就派上用场了，我们让 p=p->fail，然后继续这 2 个过程。

// js 使用数组关联父子节点
MAX_LEN = 128; // 字符范围
// 辅助结点类
class ACNode {
  constructor(data) {
    this.data = data;
    this.children = new Array(MAX_LEN);
    this.isEndingChar = false;
    this.length = 0;
    this.fail = null;
  }
}

class ACTree {
  constructor(data) {
    this.root = new ACNode('/')
  }
  // 插入字符串
  insert(text) {
    let node = this.root;
    for (let char of text) {
      let index = char.charCodeAt() + 1;
      if (!node.children[index]) {
        node.children[index] = new ACNode(char);
      }
      node = node.children[index];
    }
    node.isEndingChar = true;
    node.length = text.length;
  }
  // 构建失败指针
  buildFailurePointer() {
    let root = this.root;
    let queue = [];
    queue.push(root);
    while (queue.length > 0) {
      let p = queue.shift();
      for (let i = 0; i < MAX_LEN; i++) {
        let pc = p.children[i];
        if (!pc)  continue;
        if (p == root) {
          pc.fail = root;
        } else {
          let q = p.fail;
          while (q) {
            let qc = q.children[pc.data.charCodeAt() + 1];
            if (qc) {
              pc.fail = qc;
              break;
            }
            q = q.fail;
          }
          if (!q) pc.fail = root;
        }
        queue.push(pc);
      }
    }
  }
  // 匹配字符串
  match(text) {
    let root = this.root;
    let n = text.length;
    let p = root;
    for (let i = 0; i < n; i++) {
      let idx = text[i].charCodeAt() + 1;
      while (!p.children[idx] && p != root) {
        p = p.fail;
      }
      p = p.children[idx];
      if (!p) p = root;
      let tmp = p;
      while (tmp != root) {
        if (tmp.isEndingChar == true) {
          console.log(`Start from ${i - p.length + 1}, length: ${p.length}`);
        }
        tmp = tmp.fail;
      }
    }
  }
}

// js 使用 map 关联父子结点
// 节点辅助类
class ACNode {
  constructor(data) {
    this.data = data;
    this.children = new Map();
    this.isEndingChar = false;
    this.length = 0;
    this.fail = null;
  }
}

class ACTree {
  constructor(data) {
    this.root = new ACNode('/')
  }
  // 插入一个模式串
  insert(text) {
    let node = this.root;
    for (let char of text) {
      if (!node.children.get(char)) {
        node.children.set(char, new ACNode(char));
      }
      node = node.children.get(char);
    }
    node.isEndingChar = true;
    node.length = text.length;
  }
  // 构建失败指针
  buildFailurePointer() {
    let root = this.root;
    let queue = []; // 顺序队列
    queue.push(root);
    while (queue.length > 0) {
      let p = queue.shift();
      for (var pc of p.children.values()) {
        if (!pc) continue;
        if (p == root) {
          pc.fail = root;
        } else {
          let q = p.fail;
          while (q) {
            let qc = q.children.get(pc.data);
            if (qc) {
              pc.fail = qc;
              break;
            }
            q = q.fail;
          }
          if (!q) pc.fail = root;
        }
        queue.push(pc);
      }
    }
  }
  // 匹配字符串
  match(text) {
    let root = this.root;
    let n = text.length;
    let p = root;
    for (let i = 0; i < n; i++) {
      let char = text[i];
      while (!p.children.get(char) && p != root) {
        p = p.fail;
      }
      p = p.children.get(char);
      if (!p) {
        p = root;
      }
      let tmp = p;
      while (tmp != root) {
        if (tmp.isEndingChar == true) {
          console.log(`Start from ${i - p.length + 1}, length: ${p.length}`);
        }
        tmp = tmp.fail;
      }
    }
  }
}

AC 自动机算法的时间复杂度

整个 AC 自动机算法包含两个部分，第一部分是将多个模式串构建成 AC 自动机，第二部分是在 AC 自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成 Trie 树，另一个是在 Trie 树上构建失败指针。
构造 Trie 树的时间复杂度为 O(mlen)，其中 len 表示敏感词的平均长度，m 表示敏感词的个数。
构建失败指针时，假设 Trie 树中总的节点个数是 k，而 while 循环执行的次数不会超过树的高度 len，则单个节点构建失败指针的次数为 O(len)，所以整个构建过程的时间复杂度为 O(klen)
匹配时 for 循环依次遍历主串中的每个字符，for 循环最耗时的 while 循环部分的时间复杂度也是 O(len)，则总的匹配时间复杂度为 O(n*len)。因为敏感词并不会很长，时间复杂度可能近似于 O(n)