字符串匹配

May 26, 2022 14056

字符串匹配

在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。

BF 算法

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。

在主串中，检查起始位置分别是 0、1、2….n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

BF 算法实例

最坏情况时间复杂度是 O(n*m)

RK 算法

RK 算法的全称叫 Rabin-Karp 算法，是 BF 算法的升级版

RK 算法的思路

通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

提高哈希算法计算子串哈希值的效率

假设要匹配的字符串的字符集中只包含 K 个字符，可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。

相邻两个子串 s[i-1]和 s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，也就是说，可以使用 s[i-1]的哈希值很快的计算出 s[i]的哈希值。

26(m-1) 这部分的计算，我们可以通过查表的方法来提高效率。事先计算好 260、261、262、263……26(m-1) ，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标，需要计算 26 的 x 次方的时候，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。

问题：模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表示的范围，那该如何解决呢？

为了能将哈希值落在整型数据范围内，可以允许哈希冲突

RK 算法的时间复杂度

整个 RK 算法包含两部分

  1. 计算子串哈希值和模式串哈希值

    通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)

  2. 子串哈希值之间的比较

    时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)

RK 算法整体的时间复杂度就是 O(n)

最坏情况时间复杂度O(n*m)

BF、RK算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public static int bF(String a,String b) {
		int m=a.length(),n=b.length(),k;
		char[] a1=a.toCharArray();
		char[] b1=b.toCharArray();
		for(int i=0;i<=m-n;i++) {
			k=0;
			for(int j=0;j<n;j++) {
				if(a1[i+j]==b1[j]) {
					k++;
				}
				else
					break;
			}
			if(k==n) {
				return i;
			}
		}
		return -1;
	}


public static int rK(String a,String b) {
		int m=a.length(),n=b.length(),s,j;
		int[] hash=new int[m-n+1];
		int[] table=new int[26];
		char[] a1=a.toCharArray();
		char[] b1=b.toCharArray();
		s=1;
		//将26的次方存储在一个表里，取的时候直接用,虽然溢出，但没啥问题
		for(j=0;j<26;j++) {
			table[j]=s;
			s*=26;
		}
		for(int i=0;i<=m-n;i++) {
			s=0;
			for(j=0;j<n;j++) {
				s+=(a1[i+j]-'a')*table[n-1-j];
			}
			hash[i]=s;
		}
		s=0;
		for(j=0;j<n;j++) {
			s+=(b1[j]-'a')*table[n-1-j];
		}
		for(j=0;j<m-n+1;j++) {
			if(hash[j]==s) {
				return j;
			}
		}
		return -1;
	}

BM（Boyer-Moore）算法

BM 算法的核心思想

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。

  1. 坏字符规则

    BM 算法的匹配顺序实例

    BM 算法的匹配顺序是按照模式串下标从大到小的顺序

    从模式串的末尾往前倒着匹配，当发现某个字符没法匹配的时候，把这个没有匹配的字符叫作坏字符（主串中的字符）。

    1. 坏字符 c 在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符 c 与模式串中的任何字符都不可能匹配。可以将模式串直接往后滑动三位，将模式串滑动到 c 后面的位置，再从模式串的末尾字符开始比较。

      BM 算法的匹配顺序1

    2. 模式串中最后一个字符 d，还是无法跟主串中的 a 匹配，这个时候，不能将模式串往后滑动三位。因为这个时候，坏字符 a 在模式串中是存在的，模式串中下标是 0 的位置也是字符 a。这种情况下，我们可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。

      BM 算法的匹配顺序2

    当发生不匹配的时候，把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。

    BM 算法坏字符规律

    如果坏字符在模式串里多处出现，在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

    最好情况时间复杂度：O(n/m)

    问题：根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。

  2. 好后缀规则

    把已经匹配的 bc 叫作好后缀，记作{u}

    1. 拿 {u} 在模式串中查找，如果找到了另一个跟 {u} 相匹配的子串 {u*} ，就将模式串滑动到子串{u*}与主串中{u}对齐的位置。

    2. 如果好后缀在模式串中不存在可匹配的子串，在一步一步往后滑动模式串的过程中，只要主串中的 {u} 与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中 {u} 的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。

      所以，针对这种情况，不仅要看好后缀在模式串中，是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。

      从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是 {v} ，然后将模式串滑动到如图所示的位置。

分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数

BM 算法代码实现

如何查找坏字符在模式串中出现的位置?

可以将模式串中的每个字符及其下标都存到散列表中。这样就可以快速找到坏字符在模式串的位置下标了。

假设字符串的字符集不是很大，每个字符长度是 1 字节，用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。

1
2
3
4
5
6
7
8
9
10
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
  }
  for (int i = 0; i < m; ++i) {
    int ascii = (int)b[i]; // 计算b[i]的ASCII值
    bc[ascii] = i;
  }
}

变量 b 是模式串，m 是模式串的长度，bc 表示散列表

不考虑好后缀规则，仅用坏字符规则，并且不考虑 si-xi 计算得到的移动位数可能会出现负数的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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; // 坏字符对应模式串中的下标是j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    // 这里等同于将模式串往后滑动j-bc[(int)a[i+j]]位
    i = i + (j - bc[(int)a[i+j]]); 
  }
  return -1;
}

好后缀规则

  1. 在模式串中，查找跟好后缀匹配的另一个子串；
  2. 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串；

在模式串和主串正式匹配之前，通过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置

  1. 表示模式串中不同的后缀子串

    后缀子串的最后一个字符的位置是固定的，下标为 m-1，只需要记录长度就可以了。通过长度，可以确定一个唯一的后缀子串。

  2. 引入关键变量 suffix 数组

    suffix 数组的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值

    suffix 数组

  3. 引入 boolean 类型的 prefix 数组

    记录模式串的后缀子串是否能匹配模式串的前缀子串

    prefix 数组

拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。

suffix 数组、prefix 数组计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 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]) { // 与b[0, m-1]求公共后缀子串
      --j;
      ++k;
      suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
    }
    if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
  }
}

在模式串跟主串匹配的过程中，遇到不能匹配的字符时，如何根据好后缀规则，计算模式串往后滑动的位数？

  1. 假设好后缀的长度是 k。先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。

  2. 如果 suffix[k]等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段

    好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k]等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。

  3. 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，就将整个模式串后移 m 位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 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);
  int i = 0; // j表示主串与模式串匹配的第一个字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    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 - suffix[k] +1;
  for (int r = j+2; r <= m-1; ++r) {
    if (prefix[m-r] == true) {
      return r;
    }
  }
  return m;
}

KMP 算法

KMP 算法基本原理

在模式串和主串匹配的过程中，把不能匹配的那个字符叫作坏字符，把已经匹配的那段字符串叫作好前缀。

当遇到坏字符的时候，把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。

只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。

好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

next 数组

KMP 算法可以提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。把这个数组定义为 next 数组，也叫失效函数（failure function）。

数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标。

匹配发生冲突时，查看坏字符前一位的next数组下标

模式串 a a b a a f
前缀表（next数组） 0 1 0 1 2 0

next 数组算法实现

  1. 初始化
  2. 前后缀不相同情况
  3. 前后缀相同情况
  4. next数组

i 表示 后缀末尾位置

j 表示 前缀末尾位置、i之前包括i的字串的的最长相等前后缀的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
public void getNext(int[] next, char[] s) {
  int j = 0;
  next[] = 0;
  for(int i = 1; i < s.size ; i++){
    while(j > 0 && s[i] != s[j]){
      j = next[ j - 1 ];
    }
    if(s[i] == s[j]){
      j++;
      next[i] = j;
    }
  }
}

KMP 算法复杂度分析

KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。

KMP 算法的时间复杂度就是 O(m+n)

KMP算法算法实现

1

Trie树

Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

有 6 个字符串，它们分别是：how，hi，her，hello，so，see。希望在里面多次查找某个字符串是否存在。

对这 6 个字符串做一下预处理，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。

Trie 树构造的分解过程

img

Trie 树构造的分解过程

如何实现一棵 Trie 树？

Trie 树主要有两个操作

  1. 一个是将字符串集合构造成 Trie 树。这个过程分解开来的话，就是一个将字符串插入到 Trie 树的过程。
  2. 另一个是在 Trie 树中查询一个字符串。

借助散列表的思想，通过一个下标与字符一一映射的数组，来存储子节点的指针

1
2
3
4
class TrieNode {
  char data;
  TrieNode children[26];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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) {
        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';
      if (p.children[index] == null) {
        return false; // 不存在pattern
      }
      p = p.children[index];
    }
    if (p.isEndingChar == false) return false; // 不能完全匹配，只是前缀
    else return true; // 找到pattern
  }

  public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
    public boolean isEndingChar = false;
    public TrieNode(char data) {
      this.data = data;
    }
  }
}

复杂度分析

  1. 时间复杂度

    构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）

    每次查询时，如果要查询的字符串长度是 k，只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

  2. 空间复杂度

    用数组来存储一个节点的子节点的指针。如果字符串中包含从 a 到 z 这 26 个字符，那每个节点都要存储一个长度为 26 的数组，并且每个数组元素要存储一个 8 字节指针（或者是 4 字节，这个大小跟 CPU、操作系统、编译器等有关）。而且，即便一个节点只有很少的子节点，远小于 26 个，比如 3、4 个，我们也要维护一个长度为 26 的数组。

    在某些情况下，Trie 树不一定会节省存储空间。在重复的前缀并不多的情况下，Trie 树不但不能节省内存，还有可能会浪费更多的内存。

Trie 树与散列表、红黑树

Trie 树对要处理的字符串有极其严苛的要求

  1. 第一，字符串中包含的字符集不能太大。即便可以优化，但也要付出牺牲查询、插入效率的代价。
  2. 第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。
  3. 第三，如果要用 Trie 树解决问题，那就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。
  4. 第四，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

针对在一组字符串中查找字符串的问题，我们在工程中，更倾向于用散列表或者红黑树

AC 自动机(Trie 树优化)

基于单模式串和 Trie 树实现的敏感词过滤

多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。

只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在，从而大大提高匹配效率。

Trie 树就是一种多模式串匹配算法

可以对敏感词字典进行预处理，构建成 Trie 树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，只需要动态更新一下 Trie 树就可以了。

当用户输入一个文本内容后，把用户输入的内容作为主串，从第一个字符（假设是字符 C）开始，在 Trie 树中匹配。当匹配到 Trie 树的叶子节点，或者中途遇到不匹配字符的时候，我们将主串的开始匹配位置后移一位，也就是从字符 C 的下一个字符开始，重新在 Trie 树中匹配。

经典的多模式串匹配算法：AC 自动机

AC 自动机算法，全称是 Aho-Corasick 算法。

AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。

1
2
3
4
5
6
7
8
9
10
public class AcNode {
  public char data; 
  public AcNode[] children = new AcNode[26]; // 字符集只包含a~z这26个字符
  public boolean isEndingChar = false; // 结尾字符为true
  public int length = -1; // 当isEndingChar=true时，记录模式串长度
  public AcNode fail; // 失败指针
  public AcNode(char data) {
    this.data = data;
  }
}

AC 自动机的构建，包含两个操作：

  1. 将多个模式串构建成 Trie 树；
  2. 在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。

构建失败指针

Trie 树中的每一个节点都有一个失败指针

有 4 个模式串，分别是 c，bc，bcd，abcd；主串是 abcd。

假设沿 Trie 树走到 p 节点，也就是下图中的紫色节点，那 p 的失败指针就是从 root 走到紫色节点形成的字符串 abc，跟所有模式串前缀匹配的最长可匹配后缀子串，就是箭头指的 bc 模式串。

字符串 abc 的后缀子串有两个 bc，c，我们拿它们与其他模式串匹配，如果某个后缀子串可以匹配某个模式串的前缀，那我们就把这个后缀子串叫作可匹配后缀子串。

从可匹配后缀子串中，找出最长的一个。将 p 节点的失败指针指向那个最长匹配后缀子串对应的模式串的前缀的最后一个节点，就是图中紫色箭头指向的节点。

如果把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层。

失败指针的构建过程，是一个按层遍历树的过程

首先 root 的失败指针为 NULL，也就是指向自己。

假设节点 p 的失败指针指向节点 q，看节点 p 的子节点 pc 对应的字符，是否也可以在节点 q 的子节点中找到。如果找到了节点 q 的一个子节点 qc，对应的字符跟节点 pc 对应的字符相同，则将节点 pc 的失败指针指向节点 qc。

如果节点 q 中没有子节点的字符等于节点 pc 包含的字符，则令 q=q->fail（fail 表示失败指针），继续上面的查找，直到 q 是 root 为止，如果还没有找到相同字符的子节点，就让节点 pc 的失败指针指向 root。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//构建失败指针
public void buildFailurePointer() {
  Queue<AcNode> queue = new LinkedList<>();
  root.fail = 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) {
        pc.fail = root;
      } else {
        AcNode q = p.fail;
        while (q != null) {
          AcNode qc = q.children[pc.data - 'a'];
          if (qc != null) {
            pc.fail = qc;
            break;
          }
          q = q.fail;
        }
        if (q == null) {
          pc.fail = root;
        }
      }
      queue.add(pc);
    }
  }
}

在 AC 自动机上匹配主串

在匹配过程中，主串从 i=0 开始，AC 自动机从指针 p=root 开始，假设模式串是 b，主串是 a。

  1. 如果 p 指向的节点有一个等于 a[i]的子节点 x，我们就更新 p 指向 x，这个时候我们需要通过失败指针，检测一系列失败指针为结尾的路径是否是模式串。处理完之后，我们将 i 加一，继续这两个过程；
  2. 如果 p 指向的节点没有等于 a[i]的子节点，那失败指针就派上用场了，我们让 p=p->fail，然后继续这 2 个过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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) {
      p = p.fail; // 失败指针发挥作用的地方
    }
    p = p.children[idx];
    if (p == null) p = root; // 如果没有匹配的，从root开始重新匹配
    AcNode tmp = p;
    while (tmp != root) { // 打印出可以匹配的模式串
      if (tmp.isEndingChar == true) {
        int pos = i-tmp.length+1;
        System.out.println("匹配起始下标" + pos + "; 长度" + tmp.length);
      }
      tmp = tmp.fail;
    }
  }
}

Trie 树构建的时间复杂度是 O(m*len)，其中 len 表示敏感词的平均长度，m 表示敏感词的个数。

整个失败指针的构建过程时间复杂度是 O(k*len)， k 是 Trie 树中总的节点个数，每个节点构建失败指针的时候，最耗时的环节是 while 循环中的 q=q->fail，每运行一次这个语句，q 指向节点的深度都会减少 1，而树的高度最高也不会超过 len，所以每个节点构建失败指针的时间复杂度是 O(len)。

用 AC 自动机做匹配的时间复杂度，for 循环依次遍历主串中的每个字符，for 循环内部最耗时的部分也是 while 循环，而这一部分的时间复杂度也是 O(len)，所以总的匹配的时间复杂度就是 O(n*len)。因为敏感词并不会很长，而且这个时间复杂度只是一个非常宽泛的上限，实际情况下，可能近似于 O(n)，所以 AC 自动机做敏感词过滤，性能非常高。

查看评论