KMP算法基础
- 主要应用：在字符串匹配上。
- 主要思想：匹配过程中，当出现不匹配的字符时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
- 什么是前缀：是指不包含最后一个字符的所有以第一个字符开头的连续子串。比如字符串"aab"的前缀有：a，aa。
-
什么是后缀：是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
比如字符串"aab"的后缀有：b，ab。 - 什么是最长相同前后缀：字符串"aab"的前、后缀不存在相同的字符串，所以最长相同前后缀长度为0。
- 什么是前缀表：字符串从索引 i = 0 开始，统计 0 ~ i (包括i) 的字符串中最长相同前后缀组成的数组。
举例：字符串 "aabaaf"
详细过程：
i = 0, 字符串为 a，最长相同前后缀长度为0
i = 1, 字符串为 aa，前缀：a，后缀：a，存在1个相同的前后缀，则最长相同前后缀长度为1
i = 2, 字符串为 aab，前缀：a,aa，后缀：b,ab，不存在相同的前后缀，则最长相同前后缀长度为0
i = 3, 字符串为 aaba，前缀：a,aa,aab，后缀：a,ba,aba，存在 1 个相同的前后缀 a，则最长相同前后缀长度为1
i = 4, 字符串为 aabaa，前缀：a,aa,aab,aaba，后缀：a,aa,baa,abaa，存在 2 个相同的前后缀 a 和 aa，则最长相同前后缀为2
i = 5, 字符串为 aabaaf，前缀：a,aa,aab,aaba,aabaa，后缀：f,af,aaf,baaf,abaaf，存在 0 个相同的前后缀，则最长相同前后缀为0
所以其前缀表为[0, 1, 0, 1, 2, 0]
- 前缀表的作用：
举例：文本串"aabaabaafa"，模式串"aabaaf"
image.png
如图，当匹配到下标 i = 5时，当出现 b 和 f 不匹配的字符时，下一步可以直接跳到下标为 2 的位置继续匹配。
至于为什么是跳转到下标为2的位置，是根据前缀表来的
下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。
-
如何构建前缀表
实现一
- 初始化两个指针
i = 0, j = -1，数组next = [j];
其中 i 指向后缀末尾位置，j 指向前缀末尾位置;
比如i = 2，指向字符b，已经匹配过的字符串为 aab，此时 i 指向后缀末尾即字符b，j 指向前缀末尾即字符a； - 处理前后缀不相同的情况
- 处理前后缀相同的情况
28. 找出字符串中第一个匹配项的下标
解题思路
var strStr = function(haystack, needle) {
if (needle.length === 0) {
return 0;
}
// 初始化j=-1
let j = -1;
let next = []
next.push(j);
// 遍历模式字符串
for (let i = 1; i < needle.length; i++) {
// 前后缀不相同
while(j >= 0 && needle[i] !== needle[j+1]) {
j = next[j] // 向前回退
}
// 前后缀相同
if (needle[i] === needle[j+1]) {
j++
}
next.push(j)
}
j = -1;
for (let i = 0; i < haystack.length; i++) {
while(j >= 0 && haystack[i] !== needle[j+1]) {
j = next[j]
}
if (haystack[i] === needle[j+1]) {
j++
}
if (j == (needle.length - 1) ) { // 文本串s里出现了模式串t
return (i - needle.length + 1);
}
}
return -1
};
