字符串匹配
BF算法
暴力匹配算法，Brute Force，简称BF，也叫朴素匹配算法，简单、好懂，但是相应的性能不高。
在字符串A中查找字符串B，A叫做主串，长度为n，B叫做模式串，长度为m。因为我们是在主串中查找模式串，所以n>m。
BF的思想是：在主串中，检查起始位置分别是0,1,2…n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。示意图如下：
从上图可以看出，最坏情况是主串为”aaaaa….aaa”，模式串是”aaaaab”，每次都要比对m个字符，要比对n-m+1，即最坏时间复杂度是O((n-m+1)*m)=O(n*m)。
实际开发中，BF算法是一种比较常用的算法，主要原因有：
- 实际开发的软件中，大部分情况下，模式串和主串的长度都不会太长，尽管理论上的最坏时间复杂度是O(n*m)，但是算法执行效率要比这个高很多
- BF思想简单，代码实现也非常简单。在工程中，满足性能要求的前提下，简单是首选，即KISS(Keep it Simple and Stupid)设计原则
RK算法
Rabin-Karp算法，简称RK算法，是根据两位发明者Rabin和Karp的名字来命名的。核心思想是通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小即可判断子串和模式串是否匹配。因为哈希值是一个数字，比较的效率就提高了很多，示意图如下：
哈希算法的选择有一定技巧，假设要匹配的字符串的字符集中只包含K个字符，可以用一个K进制数来表示一个子串，将这个K进制数转化成十进制树作为子串的哈希值。如要处理的字符串只包含a-z则25个小写字母，用二十六进制来表示一个字符串，将a-z映射到0-25这26个数字，a为0，z为26，则哈希值的计算方式如下：
这种哈希算法有一个特点，相邻两个子串s[i-1]和s[i]，i表示子串在主串中的起始位置，子串的长度都为m，对应的哈希值计算公式有交集，示意图如下：
注：图中最后一个公式少一个右括号。
公式中26^(m-1)的计算有一个技巧，提前计算好放到一个表中来提高效率，示意图如下：
整个RK算法，包含两部分：
- 计算子串哈希值，由于设计的特殊哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值，所以这部分的时间复杂度是O(n)
- 模式串哈希值与子串哈希值比较的时间复杂度是O(1)，总共需要比较n-m+1个子串的哈希值，所以这部分的时间复杂度是O(n)
综上，整个RK算法的时间复杂度是O(n)。
为了避免哈希冲突产生误判，在比较子串和模式串的哈希值相等之后，再逐一比较子串和模式串是否真的相等即可。
哈希算法的冲突概率要相对控制的低一些，如果存在大量冲突，就会导致RK算法的时间复杂度退化，效率下降，极端情况下会退化为O(n*m)。
BM算法
Boyer-Moore，简称BM算法，是一种非常高效的字符串匹配算法。核心思想是在模式串与主串匹配的过程中，当模式串的主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。
BM算法包含两部分，分别是坏字符规则(Bad Character Rule)和好后缀规则(Good Suffix Shift)，后者可以独立于前者使用，因为前者的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现BM算法。
坏字符规则
BF和RK在匹配过程中，按照模式串的下标从小到大的顺序，而BM算法是从大到小的顺序匹配，示意图如下：
对于某个字符时没法匹配的时候，该主串中的字符叫做坏字符。
好后缀规则
已经匹配的bc叫做好后缀，示意图如下：
通过计算坏字符和好后缀规则往后滑动的位数，然后去两个数中最大的，作为模式串往后滑动的位数，该方法还能避免根据坏字符规则计算得到的滑动位数为负数的情况。
KMP算法
KMP算法是根据三位作者(D.E.Knuth, J.H.Morris和V.R.Pratt)的名字来命名的，算法的全称是Knuth Morris Pratt算法，简称KMP。
KMP的核心和BM一样，在匹配到坏字符之后，把模式串往后多滑动几位。
Trie树
Trie树，也叫“字典树”，是一个树形结构，是一种专门处理字符串匹配的数据结构，用来解决一组字符串集合中快速查找某个字符串的问题，非常的高效。Trie树的核心思想是利用字符串之间的公共前缀，将重复的前缀合并在一起。
假如我们有6个字符串：how, hi,her,hello,so,see，则构造的Trie树为：
其中根节点不包含任何信息，每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串(注意：红色节点并不都是叶子节点)，Trie树的构造过程如下：
Trie树的实现
借助散列表的思想，通过一个下标与字符意义映射的数组，来存储子节点的指针，示意图如下：
Trie树的代码实现如下：
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;
}
}
}
构建Trie树的过程，需要扫描所有的字符串，时间复杂度是O(n)，n表示所有字符串的长度和。构建好Trie树之后，在其中查找字符串的时间复杂度是O(k)，k表示要查找的字符串的长度。
Trie树非常消耗内存
Trie用数组来存储一个节点的子节点的指针，当字符串中包含小写、大写、数字甚至中文时，需要的存储空间会非常高，在重复的前缀并不多的情况下，Trie树不但不能节省内存，还有可能浪费更多的内存。
改进方法是不用数组来存储所有可能的子节点组合，而是用动态数据结构如有序数组、跳表、散列表、红黑树来实现，在插入元素的是否，需要维护相应的数据结构保持其特性，牺牲了一点时间减少了空间浪费。
Trie树变体有很多，还有一种是缩点优化，可以节省空间，但是增加了编码难度，示意图如下：
Trie树 VS 散列表 VS 红黑树
对于Trie树：
- 字符串中包含的字符集不能太大
- 要求字符串的前缀重合比较多，不然空间消耗会变大很多
- 如果要用Trie树解决问题，需要自己写Trie树，保证没有bug，在工程上，除非必须，一般不建议这样做
- Trie使用了指针串起来数据，对于CPU缓存不够友好
综上，在工程中，针对在一组字符串中查找字符串的问题，更倾向于用散列表或者红黑树，因为可以直接利用编程语言中提供的线程类库即可。
利用Trie树实现搜索关键词的提示功能
假设关键词库（仅包含字母）由用户的热门搜索关键词组成，利用该词库构建一个Trie树，用户输入其中单词的时候，将该词在Trie树中匹配，展示匹配结果即可，示意图如下：
Trie树的应用可以扩展到自动输入补全，如输入法的自动补全功能、IDE代码编辑器自动补全功能、浏览器网址输入的自动补全功能等。
AC自动机
字符串匹配算法有：
- BF
- RK
- BM
- KMP
- Trie
前面四种都是单模式串匹配算法，Trie树是多模式串匹配算法。
单模式串匹配算法是指在一个主串中查找一个模式串，多模式串匹配算法指在多个模式串和一个主串之间做匹配，即在一个主串中查找多个模式串。
AC自动机算法，全称是Aho-Corasick算法。AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上罢了。
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自动机的构建，包含两个操作：
- 将多个模式串构建成Trie树
- 在Trie树上构建失败指针，相当于KMP中的失效函数next数组
构建失败指针的代码如下：
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自动机如下：
匹配过程代码如下：
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;
}
}
}
AC自动机构建Trie树过程的时间复杂度是O(m*len)，len表示敏感词的平均长度，m表示敏感词的个数；构建失败指针的时间复杂度是O(k*len)，k是Trie树总的节点个数。但是AC自动机的构建过程是预先处理好的，构建好之后，并不会频繁更新，所以不会影响到敏感词过滤的效率。
查询时，AC自动机的时间复杂度是O(n*len)，实际情况敏感词可能不会很长，可能近似与O(n)，所有AC自动机做敏感词过滤，性能非常高。极端情况下，AC自动机的性能才会退化到更Trie树一样，示意图如下：
字符串匹配总结
一、单模式串匹配：
- BF： 简单场景，主串和模式串都不太长, O(m*n)
- KP：字符集范围不要太大且模式串不要太长， 否则hash值可能冲突，O(n)
- naive-BM：模式串最好不要太长（因为预处理较重），比如IDE编辑器里的查找场景； 预处理O(m*m), 匹配O(n)， 实现较复杂，需要较多额外空间.
- KMP：适合所有场景，整体实现起来也比BM简单，O(n+m)，仅需一个next数组的O(n)额外空间；但统计意义下似乎BM更快，原因不明.
二、多模式串匹配：
- naive-Trie: 适合多模式串公共前缀较多的匹配(O(n*k)) 或者 根据公共前缀进行查找(O(k))的场景，比如搜索框的自动补全提示.
- AC自动机: 适合大量文本中多模式串的精确匹配查找, 可以到O(n).
注：本文是《数据结构与算法之美》的读书笔记，配套代码地址GitHub。本文仅限个人学习，请勿用作商业用途，谢谢。
Note: Cover Picture