String Matching
在字符串 A 中查找字符串 B，A 叫做主串，B 叫做模式串。
Brute Force，暴力匹配算法或朴素匹配算法。
思想：主串长度为 n，模式串长度为 m，在主串中，从起始位置 0、1、2 ... n-m 且长度为 m 的 n - m + 1 个子串中，看有没有和模式串匹配的。
最差时间复杂度 O(n*m)，最差情况下，每次需要对比 m 个字符，需要对比 n - m + 1 次。
尽管 BF 算法的时间复杂度很高，但是实际开发中较常用，原因是：
- 大部分情况下，模式串和主串都不太长。
- 每次模式串与主串中的子串比较时，中途遇到不能匹配的，就能提前停止，大部分情况不会达到最差时间复杂度。
- 思想简单，实现简单，不易出错。
Rabin-Karp 算法，由两位发明者命名的。
BF 算法中，每次模式串与主串的子串比较时，都需要比较模式串的每个字符。RK 的核心思路就是计算 n - m + 1 个子串的 hash 值，然后与模式串的 hash 值比较，hash 的比较就非常快了。
但是所有子串计算 hash 值的时候还是要遍历每个子串的所有字符，此时就需要设计一个 hash 算法来优化。
核心思路是 hash 值的计算可以利用前一个子串的计算结果。比如：假设匹配的字符串的字符集只有 K 个字符，可以用 K 进制数来表示一个字符，转换为 10 进制数作为 hash 值。
时间复杂度 O(n)。
如果考虑 hash 冲突，在 hash 值相等后还需要比较原始的字符串。
Boyer-Moore 算法包含两部分，坏字符规则（bad character rule）和好后缀规则（good suffix shift）。
模式串与主串的匹配过程可以看做是模式串不断在主串中往后移动。当遇到不匹配时，BF、RK 算法是模式串往后移动一位；BM 算法的本质就是寻找规则，让模式串尽可能往后多移动几位。
首先是按照模式串下标从大到小倒着匹配。当发现某个字符（坏字符）无法匹配时，坏字符对应模式串中的下标为 si，然后拿这个坏字符在模式串中从后往前查找，找到下标为 xi，若没有找到 xi = -1，那么模式串就往后移动 si - xi 位。
如下例子，从后往前匹配，c 是坏字符，si = 2，xi = -1，所以模式串往后移动 3 位。移动完成后接着匹配，a 为坏字符，si = 2，xi = 0，所以模式串往后移动 2 位。
a b c a c a b d c
a b d
a b d
a b d
最好时间复杂度：O(n/m)。主串：aaabaaabaaab，模式串：aaaa。
问题：主串：aaaaaaaaaaa，模式串：baaa，按照刚才的算法还会后退。
后缀子串：最后一个字符对齐，如 abc 的后缀子串有 c、bc。
前缀子串：起始字符对齐，如 abs 的前缀子串有 a、ab。
模式串与主串从后往前比较时，在发现坏字符时，前面已经有部分匹配了，匹配的部分叫做好后缀。如下，坏字符为 a，好后缀为 ca。
a b c a c a b d c
d b c a
原理：模式串已经匹配好的好后缀部分记做 {u}，然后好后缀在模式串中继续查找，找另一个与 {u} 匹配的 {u*}：
- 若能找到 u{*}，就将模式串滑动到 {u*} 与主串中好后缀对齐的位置。
- 若不能找到 u{*}，就查看好后缀的后缀子串是否存在与模式串的前缀子串匹配的情况，并找到最长的 {v}，然后模式串滑动到 {v} 与主串中 {v} 对齐的部分。
// {u} = de，情况 1 能找到 {u*}
a b c d e f g
d e a d e
d e a d e
// {u} = de，情况 2 不能找到 {u*}，{v} = d
a b c d e f g
e a a d e
e a a d e
分别计算好后缀和坏字符规则的滑动长度，取最长的滑动。
KMP 算法与 KM 本质一样，在模式串与主串匹配过程中，若遇到不匹配的，则寻找规律尽量使模式串多往后移动几位。
Trie 树，也叫字典树。专门用于处理字符串匹配的数据结构，解决在一组字符串集合中快速查找某个字符串的问题。
本质：利用字符串之间的公共前缀，将重复的前缀合并在一起。
如下图所示，根节点不包含任何信息，每个节点表示一个字符串中的字符，从根节点到红色节点的路径表示一个字符串。注意：红色节点不一定为叶子节点。
// 假设字符串中只有 a~z 26个小写字母。这种存储方式比较消耗内存。
// 节点可以换成其它数据结构来节约内存，比如跳表、散列表、红黑树等
class TrieNode {
char data;
TrieNode children[26];
public boolean isEndingChar = false;
}
时间复杂度：构建 Trie 树为 O(n)，n 表示所有字符串长度总和，构建仅需一次；查找为 O(k)，k 为需要查找字符串的长度。
适用条件：
- 字符集不能太多，不然会消耗很多内存；若节点改成其它数据结构，就会降低效率。
- 字符串前缀重复较多。
适用场景：
- 自动不全
- 搜索关键字提示
与散列表、红黑树比较：精确匹配适合散列表、红黑树等数据结构；前缀匹配适合 Trie 树。
Aho–Corasick 算法是基于 Trie 树的一种改进算法。
Last modified 3yr ago