字符串匹配算法很多，
- 单模式串匹配的算法，也就是一个串跟一个串进行匹配。
两种比较简单的、好理解的，它们是：BF 算法和 RK 算法；
两种比较难理解、但更加高效的，它们是：BM 算法和 KMP 算法； - 多模式串匹配算法，也就是在一个串中同时查找多个串。
包括 Trie 树和 AC 自动机。
BF 算法（Brute Force）
BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。
比方说，我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m。
BF 算法的思想可以用一句话来概括，那就是，我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。
时间复杂度也比较高，是 O(n*m)。
不过，在实际的软件开发中，因为这种算法实现简单，对于处理小规模的字符串匹配很好用。
RK 算法（Rabin-Karp）
RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。
RK 算法是 BF 算法的改进，它巧妙借助了我们前面讲过的哈希算法，让匹配的效率有了很大的提升。
RK 算法的思路是这样的：
我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
这就需要哈希算法设计的非常有技巧了。我们假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值。
理想情况下，RK 算法的时间复杂度是 O(n)，跟 BF 算法相比，效率提高了很多。不过这样的效率取决于哈希算法的设计方法，如果存在冲突的情况下，时间复杂度可能会退化。极端情况下，哈希算法大量冲突，时间复杂度就退化为 O(n*m)。
BM算法（Boyer-Moore）
BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的 3 到 4 倍。BM 算法的原理很复杂，比较难懂，学起来会比较烧脑。
BM 算法的核心思想
在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。
BM 算法原理分析
BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。
1. 坏字符规则
BM匹配顺序.png
BM 算法的匹配顺序比较特别，它是按照模式串下标从大到小的顺序，倒着匹配的。
从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。比如此处的c。
坏字符.png
当发生不匹配的时候，我们把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作 xi。如果不存在，我们把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，我这里说的下标，都是字符在模式串的下标）。
特别说明一点，如果坏字符在模式串里多处出现，那我们在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。
2. 好后缀规则
好后缀.png
好后缀移动.png
我们把已经匹配的 bc 叫作好后缀，记作{u}。我们拿它在模式串中查找，如果找到了另一个跟{u}相匹配的子串{u}，那我们就将模式串滑动到子串{u}与主串中{u}对齐的位置。
如果在模式串中找不到另一个等于{u}的子串，我们就直接将模式串，滑动到主串中{u}的后面。
好后缀的过度滑动.png
如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中，只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。
好后缀与模式串重叠.png
所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。
好后缀的后缀子串 vs 模式串的前缀子串.png
3. 坏字符/好后缀 如何选择
当模式串和主串中的某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后滑动的位数？
我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免我们前面提到的，根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。
BM 算法代码实现
坏字符的移动.png
BM 算法的性能分析及优化
实际上，BM 算法的时间复杂度分析起来是非常复杂，这篇论文“A new proof of the linearity of the Boyer-Moore string searching algorithm”证明了在最坏情况下，BM 算法的比较次数上限是 5n。这篇论文“Tight bounds on the complexity of the Boyer-Moore string matching algorithm”证明了在最坏情况下，BM 算法的比较次数上限是 3n。你可以自己阅读看看。
BM 算法总结
BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。BM 算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现 BM 算法。
KMP算法（Knuth Morris Pratt）
KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名的，算法的全称是 Knuth Morris Pratt 算法，简称为 KMP 算法。
KMP 算法的核心思想，跟前面的 BM 算法非常相近。
我们假设主串是 a，模式串是 b。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
好前缀/坏字符.png
在模式串和主串匹配的过程中，把不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。
当遇到坏字符的时候，我们就要把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。这个比较的过程能否更高效了呢？可以不用一个字符一个字符地比较了吗？
KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？
我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k（前面k位是好前缀的前缀字串{v}），i 不变，然后继续比较。
image.png
image.png
next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀/后缀。
例如next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
匹配失配，j = next [j]，模式串向右移动的位数为：j - next[j]。
换言之，当模式串的后缀Pj-k Pj-k+1, ..., Pj-1 跟文本串Si-k Si-k+1, ..., Si-1匹配成功，但Pj 跟Si匹配失败时，因为next[j] = k，相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀，即P0 P1 ...Pk-1 = Pj-k Pj-k+1...Pj-1，故令j = next[j]，从而让模式串右移j - next[j] 位，使得模式串的前缀P0 P1, ..., Pk-1对应着文本串 Si-k Si-k+1, ..., Si-1，而后让Pk 跟Si 继续匹配。如下图所示：
S[i]/P[j]匹配失败.png
当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。
如果用数学公式来表示是这样的 P[0 ~ k-1] == P[j-k ~ j-1]，如下图：
匹配失败时next[j]=k.png
弄明白了这个就应该可能明白为什么可以直接将j移动到k位置了。
因为:
当T[i] != P[j]时
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]
...[待补充]
极客时间--数据结构与算法之美--32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？
极客时间--数据结构与算法之美--33 | 字符串匹配基础（中）：如何实现文本编辑器中的查找功能？
极客时间--数据结构与算法之美--34 | 字符串匹配基础（下）：如何借助BM算法轻松理解KMP算法？
KMP算法详解-彻底清楚了(转载+部分原创)
从头到尾彻底理解KMP（2014年8月22日版）
网友评论