字符串匹配算法
朴素解法
朴素解法是最简单易懂的：
枚举字符串中的每个字符作为发起点，每次将发起点和匹配字符串的首位进行比较。
- 匹配成功：返回发起点。
- 匹配失败：枚举字符串中下一个发起点，重新尝试匹配。
function strStr(s, p) {
const n = s.length,
m = p.length
for (let i = 0; i <= n - m; i++) {
let cpyI = i,
cur = 0
while (k < m && s[cpyI] === p[cur]) {
cpyI++
cur++
}
if (k === m) return i
}
return -1
}
该算法时间复杂度为 $O((n-m)*m)$，空间复杂度为 $O(1)$。
KMP 算法
KMP 算法与朴素解法不同，KMP 是通过非完全匹配提取有效信息，减少重复匹配的消耗。
朴素解法在匹配失败的情况下会调整到下一个发起点进行匹配，而 KMP 算法在匹配失败的情况下是这样的：
匹配字符串会检查之前已经匹配成功的部分中是否有相同的前缀和后缀，如果有，则跳转到前缀的下个位置继续匹配。
例如：原字符串为 ississmissp，匹配字符串为 issp。
第一次匹配，前三个字符匹配，第四个不匹配：
i s s i s s m i s s p
| | | ×
i s s p
检查共同前缀和后缀，发现前三个字符iss为共同前缀，因此直接跳过这三个字符，从第四个字符开始比较：
i s s i s s m i s s p
| | | ×
i s s p
不匹配，但有共同前缀，因此跳过共同前缀：
i s s i s s m i s s p
×
i s s p
第一个字符就不匹配，但发现后缀iss匹配，因此跳到下一个位置：
i s s i s s m i s s p
| | | |
i s s p
匹配，完成搜索。
KMP 利用已匹配部分的共同前缀和后缀加速下一次的匹配，因此比朴素解法更快。
然而相对于朴素算法，我们需要在每次匹配之后找出共同前缀和后缀，这一步该怎么办？
我们可以看出从匹配字符串的某个位置跳转到下一个匹配位置这个过程与原字符串是无关的。
在 KMP 算法中我们需要先计算目标字符串的部分匹配表，这个表是如何产生的呢？
首先，要了解两个概念："前缀"和"后缀"。"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
比如我们要搜索的字符串为 ABCDABD，匹配的字符串为 ABCDAB ABCDABCDABDE：
A的前缀和后缀都为空集，共有元素的长度为 0。AB的前缀为[A]，后缀为[B]，共有元素的长度为 0。ABC的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度 0。ABCD的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为 0。ABCDA的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为A，长度为 1。ABCDAB的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为AB，长度为 2。ABCDABD的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为 0。
因此我们得到部分匹配表为 [0, 0, 0, 0, 1, 2, 0]。
然后我们匹配两个字符串：
A B C D A B A B C D A B C D A B D E
| | | | | | ×
A B C D A B D
第一轮匹配后我们发现最后一个匹配成功的字符是下标为 5 的字符 B，对应部分匹配表中的值为 2，因此需要往左移动位数为已匹配的字符数 - 对应的部分匹配值，也就是 5 + 1 - 2 = 4。于是往右移 4 位继续比较：
A B C D A B A B C D A B C D A B D E
| | ×
A B C D A B D
最后一个匹配成功的字符是下标为 1 的字符 B，对应部分匹配表中的值为 0，因此需要往左移动位数为 1 + 1 - 0 = 2。
A B C D A B A B C D A B C D A B D E
×
A B C D A B D
第一个就不匹配了，因此往后移一位：
A B C D A B A B C D A B C D A B D E
| | | | | | ×
A B C D A B D
第一轮匹配后我们发现最后一个匹配成功的字符是下标为 5 的字符 B，对应部分匹配表中的值为 2，因此需要往左移动位数为 5 + 1 - 2 = 4。
A B C D A B A B C D A B C D A B D E
| | | | | | |
A B C D A B D
匹配成功！
下面是 KMP 算法的实现：
// 计算部分匹配表
function pmtArr(target) {
const result = []
target = target.split('')
for (let j = 0; j < target.length; j++) {
// 获取模式串不同长度下的部分匹配值
const pmt = target
let pmtNum = 0
for (let k = 0; k < j; k++) {
const head = pmt.slice(0, k + 1) // 前缀
const foot = pmt.slice(j - k, j + 1) // 后缀
if (head.join('') === foot.join('')) {
const num = head.length
if (num > pmtNum) pmtNum = num
}
}
// 计算出右移位数
result.push(j + 1 - pmtNum)
}
return result
}
function mapKMPStr(base, target) {
let isMatch = []
let pmt = pmtArr(target)
let times = 0
for (let i = 0; i < base.length; i++) {
times++
let tempIndex = 0
for (let j = 0; j < target.length; j++) {
if (i + target.length <= base.length) {
if (target.charAt(j) === base.charAt(i + j)) {
isMatch.push(target.charAt(j))
} else {
if (!j) break //第一个就不匹配直接跳到下一个
let skip = pmt[j - 1]
tempIndex = i + skip - 1
break
}
}
}
if (tempIndex) i = tempIndex
if (isMatch.length === target.length) {
return i
}
isMatch = []
}
return -1
}
KMP 是线性算法，处理主和匹配串的复杂度都为 $O(N)$，所以是 $O(m+n)$
Sunday 算法
KMP 理解起来真是不慎麻烦，还是看看理解难度较低的 Sunday 算法吧。
Sunday 算法关注的是原字符串中参与匹配的最末字符（并非正在匹配的）的下一位。
Sunday 算法的策略就是：
- 当遇到不匹配的字符时，如果关注的字符没有在模式串中出现，则直接跳过。
原字符串 a b c d a b d e f h a b e
| | ×
模式串 a b e
模式串 abe 中并不存在字符 d，因此需要移动 模式串.length + 1 = 4。
- 当遇到不匹配字符时，如果关注的字符在模式串中存在，其移动位数就是
模式串.length - 该字符最右出现的位置(从0开始)。
原字符串 a b c d a b d e f h a b e
×
模式串 a b e
在这个例子中，参与匹配的最末字符的下一位为 a，a 在模式串中存在，则移动 模式串.length - 0 = 3。
在举个例子：ississpississmp 和 ississm。
首先算出模式串中所有字符的偏移量：
i -> 4, s -> 2, m -> 1
进行第一次比较
原字符串 i s s i s s p i s s i s s m p
| | | | | | ×
模式串 i s s i s s m
最后一位不匹配，查看参与匹配的最末字符的下一位 i 在偏移表中的偏移量为 4，于是模式串向右移动 4 位，再次进行比较：
原字符串 i s s i s s p i s s i s s m p
×
模式串 i s s i s s m
第一个位不匹配，查看参与匹配的最末字符的下一位 s 在偏移表中对应的偏移量为 2，于是模式串向右移动 2 位，再次进行比较：
原字符串 i s s i s s p i s s i s s m p
×
模式串 i s s i s s m
第一个位不匹配，查看参与匹配的最末字符的下一位 m 在偏移表中对应的偏移量为 1，于是模式串向右移动 1 位，再次进行比较：
原字符串 i s s i s s p i s s i s s m p
| | | | | | |
模式串 i s s i s s m
匹配成功。
Sunday 的示例代码：
function sundaySearch(haystack, needle) {
if (needle === '') return 0
// 存放偏移量的对象(用Map也可以)
const offset = {}
const hLen = haystack.length
const nLen = needle.length
// 遍历needle计算偏移量
for (let i = 0; i < nLen; i++) {
offset[needle[i]] = nLen - i
}
let j,
i = 0
while (i <= hLen - nLen) {
j = 0
// 依次匹配字符
while (haystack[i + j] === needle[j]) {
j++
// 全部匹配返回i
if (j === nLen) return i
}
// 全部不匹配返回-1
if (i + nLen === hLen) return -1
// 参与匹配的最末字符的下一位是否存在于模式串中
if (offset.hasOwnProperty(haystack[i + nLen])) {
// 存在，i就跳到偏移表中当前字符
i += offset[haystack[i + nLen]]
} else {
// 不存在，i就跳过下一位
i += nLen + 1
}
}
return -1
}