概述
字符串查找函数，比如 Java 中的 indexOf()，Python 中的 find() 函数等，它们底层就是依赖字符串匹配算法。字符串匹配算法很多：
比较简单、好理解的：BF 算法和 RK 算法：模式串和主串的匹配过程，可以看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF 算法和 RK 算法的做法是，模式串往后滑动一位，然后从模式串的第一个字符开始重新匹配。
比较难理解、但更加高效的：BM 算法和 KMP 算法：匹配过程同上，遇到不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。
这些都是单模式串匹配的算法，也就是一个串跟一个串进行匹配。还有两种多模式串匹配算法，也就是在一个串中同时查找多个串，分别是 Trie 树和 AC 自动机。
BF 算法
概念
BF 算法（Brute Force），中文叫作暴力匹配算法，也叫朴素匹配算法。拿模式串与主串中的所有子串匹配，看是否有能匹配的子串。
代码实现
function brutalForce(s, p) {if (s.length === 0 || p.length === 0 || s.length < s.length) {return -1}const n = s.length, m = p.lengthfor (let i = 0; i < n; i++) {// 遍历对比子串与模式串for (let j = 0; j < m; j++) {if (s[i + j] !== p[j]) break// 如果遍历到了最后一位，并且相等，说明匹配成功if (j === p.length - 1) {// 返回已匹配子串的首字母位置return i}}}return -1}
复杂度
时间复杂度：O(n * m)。
空间复杂度：O(1)。
理论上，BF 算法的时间复杂度很高，是 O(n*m)，但在实际的开发中，它却是一个比较常用的字符串匹配算法，原因有两点：
- 在实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以大部分情况下，算法执行效率要比 O(n*m)高很多。
- 第二，朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也是常说的KISS（Keep it Simple and Stupid）设计原则。
RK 算法
概念
RK 算法（Rabin-Karp ），由两位发明者 Rabin 和 Karp 的名字来命名。其实就是 BF 算法的升级版，引入哈希算法，时间复杂度立刻降低。
通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。相等那就说明对应的子串和模式串匹配了。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
但是通过哈希算法计算子串的哈希值的时候，需要遍历子串中的每个字符。尽管模式串与子串比较的效率提高了，但是算法整体的效率并没有提高。所以需要有技巧的设计哈希算法。假设模式串中只包含 K 个字符，可以用一个 K 进制数来表示，这个 K 进制数转化成十进制数，作为模式串的哈希值。举例
比如要处理的字符串只包含 a～z 这 26 个小写字母，那就用二十六进制来表示一个字符串。把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。
在十进制的表示法中，一个数字的值是通过下面的方式计算出来的。对应到二十六进制，一个包含 a 到 z 这 26 个字符的字符串，计算哈希的时候，只需要把进位从 10 改成 26 就可以。
假设字符串中只包含 a～z 这 26 个小写字符，用二十六进制来表示一个字符串，对应的哈希值就是二十六进制数转化成十进制的结果。
这种哈希算法有一个特点，在主串中，相邻两个子串的哈希值的计算公式有一定关系：相邻两个子串s[i-1]和s[i]（i 表示子串在主串中的起始位置，子串的长度都为 m），对应的哈希值计算公式有交集，可以使用s[i-1]的哈希值很快的计算出 s[i] 的哈希值。
还有一个小细节， 26^(m-1) 这部分的计算，可以通过查表的方法来提高效率。事先计算好 26^0、26^1、26^2……26^(m-1)，并且存储在一个长度为 m 的数组中，公式中的“次方”就对应数组的下标。当需要计算 26 的 x 次方的时候，就可以从数组的下标为 x 的位置取值，直接使用，省去了计算的时间。
代码实现
```javascript // 创建a-z的映射 {a:0,b:1,…z:25} function createMapping() { const mapping = {} for (let i = 0; i < 26; i++) { const letter = String.fromCharCode(‘a’.charCodeAt() + i) mapping[letter] = i } return mapping }
// 创建字符集的映射。有多少种字符就创建多长的映射 const mapping = createMapping() // mapping的长度 const len = 26 // 求哈希值 function getHashValue(str) { let value = 0 for (let i = 0; i < str.length; i++) { value += mapping[str[i]] len * (str.length - 1 - i) } return value }
function rk(s, p) { const pHash = getHashValue(p) let sHash = getHashValue(s.slice(0, p.length))
for (let i = 0; i <= s.length - p.length; i++) { // 哈希值相等，匹配成功 if (sHash === pHash) { return i } else { // 通过首尾字符的变化，计算哈希值 // 即下一轮子串的哈希值 =（当前子串的哈希值 - 首字母的哈希值）26 + 尾部字母的哈希值 sHash = (sHash - mapping[s[i]] len * (p.length - 1)) len
+ mapping[s[i + p.length]]}
}
return -1 }
<a name="rHEpk"></a>
## 复杂度
时间复杂度：**O(n + m)**，哈希冲突时极端情况下会退化为O(n * m)。<br />空间复杂度：O(1)，主要是建立映射表的消耗。<br />问题：模式串很长，相应的主串中的子串也会很长，通过上面的哈希算法计算得到的哈希值就可能很大，如果超过了计算机中整型数据可以表示的范围，那该如何解决呢？<br />把字符串中每个字母对应的数字相加，最后得到的和作为哈希值。这种哈希算法产生的哈希值的数据范围就相对要小很多，也会降低哈希冲突。还有很多更加优化的方法，比如将每一个字母从小到大对应一个素数，而不是 1，2，3……这样的自然数，这样冲突的概率就会降低一些。<br />但是当存在哈希冲突的时候，子串和模式串的哈希值虽然是相同的，但是两者本身并不匹配。只需要再对比一下子串和模式串本身。<br />所以，哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)。但一般情况下，冲突不会很多，RK 算法的效率还是比 BF 算法高的。
<a name="amB8U"></a>
# BM算法
<a name="IdC1d"></a>
## 概念
BM（Boyer-Moore）算法是一种非常高效的字符串匹配算法，据实验统计它的性能是著名的[KMP 算法](https://zh.wikipedia.org/wiki/%E5%85%8B%E5%8A%AA%E6%96%AF-%E8%8E%AB%E9%87%8C%E6%96%AF-%E6%99%AE%E6%8B%89%E7%89%B9%E7%AE%97%E6%B3%95)的 3 到 4 倍**。**<br />BM 算法包含两部分，分别是**坏字符规则**（bad character rule）和**好后缀规则**（good suffix shift）。
<a name="N5KKf"></a>
### 1. 坏字符规则
BM 算法的匹配顺序比较特别，它是倒着匹配的：<br /><br />从模式串的末尾往前匹配，当某个字符没法匹配的时候，就把主串中没有匹配的字符叫作**坏字符**<br /><br />拿坏字符 c 在模式串中查找，如果模式串中并不存在这个字符（即字符 c 与模式串中的任何字符都不可能匹配），则将模式串直接往后滑动三位，将模式串滑动到 c 后面，再从模式串的末尾字符开始比较<br /><br />这时，模式串中最后一个字符 d，还是无法跟主串中的 a 匹配，但是坏字符 a 在模式串中是存在的，这种情况下，可以将模式串往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。<br /><br />**规律**：当发生不匹配的时候，把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作 xi。如果不存在，把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，这里的下标，都是字符在模式串的下标）。<br /><br />如果坏字符在模式串里多处出现，那 xi 选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。<br />利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是** O(n/m)**。<br />**缺点**：单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。
<a name="aAWcl"></a>
### 2. 好后缀规则
好后缀规则实际上跟坏字符规则的思路类似：<br /><br />把已经匹配的 bc 叫作好后缀，记作{u}。拿它在模式串中查找，如果找到了**另一个**跟{u}相匹配的子串{u*}，那就将模式串滑动到子串{u*}与主串中{u}对齐的位置。<br /><br />如果在模式串中找不到另一个等于{u}的子串，就直接将模式串滑动到主串中{u}的后面，因为之前的任何一次往后滑动，都没有匹配主串中{u}的情况。<br /><br />但是当模式串滑动到前缀与主串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。<br /><br />所以，不仅要看好后缀在模式串中，是否有另一个匹配的子串，还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。<br />从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是{v}，然后将模式串滑动到如图所示的位置：<br /><br />**二者使用**：可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这样还可以避免根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。
<a name="emIUK"></a>
## 代码实现
```javascript
function generateBadCharHash(p) {
// 实际生产中为了效率，可以选用映射数组或者Map
const hash = {}
for (let i = 0; i < p.length; i++) {
// 相同字符中，只关注靠后的字符
// 所以重复的字符只记录最后一次出现的位置即可
mapping[p[i]] = i
}
return hash
}
function generateGoodSuffix(p, suffix, prefix) {
const m = p.length
for (let i = 0; i < m; ++i) { // 初始化
suffix[i] = -1
prefix[i] = false
}
// i 用来标记 0 ~ i子串，和模式串寻找公共后缀
for (let i = 0; i < m - 1; ++i) {
let j = i
let k = 1 // k用来标记模式串后缀长度
// 从短到长对比子串后缀和模式串后缀
// p[j] 用来标记子串后缀的首字母
// p[m - k] 用来标记模式串后缀的首字母
while (j >= 0 && p[j] === p[m - k]) {
suffix[k] = j
j--
k++
}
// 0 ~ i子串同时也是模式串的前缀
// j == -1，表示该前缀和模式串的后缀完全相等
if (j == -1) prefix[k - 1] = true
}
}
function bm(s, p) {
const badChar = {}
generateBadChar(p, badChar)
const suffix = [], prefix = []
generateGoodSuffix(p, suffix, prefix)
const n = s.length, m = p.length
let i = 0
while (i <= n - m) {
// 从子串末尾向前遍历
let j = m - 1
while (j >= 0) {
// 找到坏字符，退出循环
if (s[j + i] !== p[j]) break
j--
}
// 如果j < 0,说明没有坏字符，字符串匹配完成，直接返回下标
if (j < 0) return i
// 计算坏字符移动位数
let bc = j
if (badChar[s[j + i]] !== undefined) {
bc = j - badChar[s[j + i]]
}
// 计算好后缀移动位数
let gs = 0
// j 比 m - 1小才会有好后缀
if (j < m - 1) {
gs = moveByGs(j, m, suffix, prefix)
}
// 从坏字符和好后缀中取较大者
// 当较大值为0的时候，移动1位
i += Math.max(bc, gs) || 1
}
return -1
}
// 创建badChar的映射，方面快速定位p中字符的位置
function generateBadChar(p, badChar) {
for (let i = 0; i < p.length; i++) {
// 相同字符中，我们只关注靠后的字符
// 所以重复的字符只记录最后一次出现的位置即可
badChar[p[i]] = i
}
}
// 预处理：生成好后缀哈希
function generateGoodSuffix(p, suffix, prefix) {
const m = p.length
// suffix，prefix数组事先申请好了
for (let i = 0; i < m; ++i) { // 初始化
suffix[i] = -1
prefix[i] = false
}
for (let i = 0; i < m - 1; ++i) {
let j = i
let k = 1 // k用来标记模式串后缀长度
// 从后往前对比子串和模式串后缀
// p[j] 用来标记子串的首字母
// p[m - k] 用来标记模式串的首字母
while (j >= 0 && p[j] === p[m - k]) {
suffix[k] = j
j--
k++
}
// 0 ~ i子串同时也是模式串的前缀
// j == -1，表示该前缀和模式串的后缀完全相等
if (j == -1) prefix[k - 1] = true
}
// console.log(suffix,prefix);
}
// 利用好后缀移动
// index: 坏字符对应的字符下标
// m，模式串长度
function moveByGs(index, m, suffix, prefix) {
const len = m - 1 - index // 好后缀长度
// 如果suffix有值，计算出移动的距离
if (suffix[len] !== -1) return index - suffix[len] + 1
for (let i = len; i > 0; i--) {
if (prefix[i]) {
// 把模式串头部对齐好后缀的后缀
return m - i
}
}
return m
}
复杂度
时间复杂度: O(n + m)（比较时间 + 预处理时间）;
空间复杂度：O(m) (预处理都跟模式串长度有关)。整个算法用到了额外的 3 个数组，其中 bc 数组的大小跟字符集大小有关，suffix 数组和 prefix 数组的大小跟模式串长度 m 有关。如果处理字符集很大的字符串匹配问题，bc 数组对内存的消耗就会比较多。因为好后缀和坏字符规则是独立的，如果我们运行的环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则，这样就可以避免 bc 数组过多的内存消耗。
KMP 算法
概念
KMP （Knuth Morris Pratt）算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字来命名。类比BM算法，在模式串和主串匹配的过程中，把不能匹配的字符仍然叫作坏字符，把已经匹配的字符串叫作好前缀。
KMP 算法思路：先从前往后遍历匹配子串和模式串，如果遇到不符合的坏字符，就把坏字符之前已经匹配好的子串看作一个整体（好前缀）。再从长到短检查好前缀的后缀，看有没有能和模式串的前缀匹配上的。
举例
拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是 k。就把模式串一次性往后滑动 j-k 位，每次遇到坏字符的时候，就把 j 更新为 k，i 不变，然后继续比较。
只需要通过模式串本身就能求解出最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。
类似 BM 算法中的 bc、suffix、prefix 数组，KMP 算法也可以提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。把这个数组定义为next 数组，很多书中还给这个数组起了一个名字，叫失效函数（failure function）。
数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标。
失效函数计算方法
KMP 算法的最复杂的部分，也就是 next 数组是如何计算出来的？
如果用非常笨的方法，比如要计算下面这个模式串 b 的 next[4]，就把 b[0, 4] 的所有后缀子串，从长到短找出来，依次看是否能跟模式串的前缀子串匹配。很显然，这个方法也可以计算得到 next 数组，但是效率非常低。
有一种更巧妙的解决方法，该方法用到了动态规划的思想。不过动态规划后面才会讲到，所以这里换种方法解释。
按照下标从小到大，依次计算 next 数组的值。当要计算 next[i] 的时候，前面的 next[0]，next[1]，……，next[i-1] 应该已经计算出来了。利用已经计算出来的 next 值，是否可以快速推导出 next[i] 的值呢？
如果 next[i-1]=k-1，也就是说，子串 b[0, k-1] 是 b[0, i-1] 的最长可匹配前缀子串。如果子串 b[0, k-1] 的下一个字符 b[k]，与 b[0, i-1] 的下一个字符 b[i] 匹配，那子串 b[0, k] 就是 b[0, i] 的最长可匹配前缀子串。所以，next[i] 等于 k。但是，如果 b[0, k-1] 的下一字符 b[k] 跟 b[0, i-1] 的下一个字符 b[i] 不相等呢？这个时候就不能简单地通过 next[i-1] 得到 next[i] 了。这个时候该怎么办呢？
假设 b[0, i] 的最长可匹配后缀子串是 b[r, i]。如果把最后一个字符去掉，那 b[r, i-1] 肯定是 b[0, i-1] 的可匹配后缀子串，但不一定是最长可匹配后缀子串。所以，既然 b[0, i-1] 最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于 b[i]，那就可以考察 b[0, 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[0, y]。于是，查找 b[0, i-1] 的次长可匹配后缀子串，这个问题就变成，查找 b[0, y] 的最长匹配后缀子串的问题了。
按照这个思路，可以考察完所有的 b[0, i-1] 的可匹配后缀子串 b[y, i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于 b[i]，那这个 b[y, i] 就是 b[0, i] 的最长可匹配后缀子串。
代码实现
function kmp(s, p) {
if (!p.length) return 0
const next = getNext(p)
const n = s.length, m = p.length
let i = 0, j = 0
while (i < s.length) {
// 遍历对比子串和模式串
while (j < m && s[i] === p[j]) {
i++
j++
}
// j === m，匹配完成
if (j === m) return i - j
// 当j === 0的时候，i后移一位
// 如果j > 0，那么i所在位置就是坏字符，下次循环需要重新对比，所以不用重新赋值
if (!j) i++
// 有公共前后缀，把j移到公共前后缀的后一位,下次循环跟i所在的坏字符对比
// 没有则退回到0的位置
j = next[j - 1] || 0
}
return -1
}
// 获取next数组
function getNext(p) {
const next = []
let len = 0
// next[0]的情况无法推出，手动初始化一下
next[0] = 0
// 通过循环推进i的下标
for (let i = 1; i < p.length; i++) {
// 对比当前公共前后缀的下一个字符
// 当len = 0，或者 找到了匹配的公共前后缀的时候，退出循环
while (len > 0 && p[i] !== p[len]) {
// 进入循环，说明当前的最长公共前后缀的下一个字符不匹配
// 就去找较短的最长公共前后缀
// 较短公共前后缀必然是较长公共前后缀的公共前后缀
// 通过next[next[i - 1] - 1],找到较短为的公共前后缀
// len = next[i - 1]
len = next[len - 1]
}
// p[i] === p[len]，表示找到了，在len的基础上 + 1就是next[i]的值
if (p[i] === p[len]) len++
// 如果 p[i] !== p[len]，表示没找到，此时len = 0，next[i] 也等于0
next[i] = len
}
return next
}
复杂度
时间复杂度：O(n + m)。
空间复杂度：O(m)，主要是建立next数组的消耗。
Sunday算法
概念
Sunday算法测试出来的效率比BM算法还高，并且更简单易懂。
从前往后遍历模式串和子串，如果发现有一个字符不匹配，直接把目标瞄到子串后面一位字符，然后查找该字符在模式串中是否存在。
如果找到了，则将模式串中匹配到的字符与该字符对齐。如果没找到，则将模式串中移动到该字符之后。
代码实现
function sunday(s, p) {
const n = s.length, m = p.length
const shift = generateShift(p)
let i = 0
while (i <= n) {
let j = 0, temp = i
// 遍历子串和模式串，进行匹配
while (s[temp] === p[j] && j < m) {
temp++
j++
}
// j === m 说明子串和模式串匹配成功，直接返回结果
if (j === m) return temp - j
// 子串后一位字符
const c = s[m - j + temp]
// 如果shift没有值，则移动m + 1位
i += shift[c] || m + 1
}
return -1
}
// 创建模式串中字符与位移距离的映射
function generateShift(p) {
const shift = {}
for (let i = 0; i < p.length; i++) {
// 相同字符中，我们只关注靠后的字符
// 所以重复的字符只记录最后一次出现的位置即可
shift[p[i]] = p.length - i
}
return shift
}
复杂度
时间复杂度: O(n + m)（比较时间 + 预处理时间）;
空间复杂度：O(m)；
若有收获，就点个赞吧
0 人点赞
