KMP 查找
Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个主文本字符串 str1 内查找一个词 str2 的出现位置。
思路
生成 next 数组
next 数组是决定了 KMP 算法的下一步匹配的位置信息。
1 根据需查找字符串 str2 生成一段 next 数组信息
2 next 数组长度与 str2 长度一致
3 next 数组每一项表达的意思是 str2 当前位置最大匹配前缀与最大匹配后缀的长度信息
最大前缀、最大后缀匹配长度
str2 当前位置前缀后缀的最大匹配字符串长度
考察[aaaaa]{i} i 前的字符
前缀不包括最后一个字符，后缀不包括第一个字符
var str2 = 'abcabcdabc'
var next = [-1, 0, 0, 0, 1, 2, 3, 0, 1, 2]
// 0 位置前方无匹配为 -1， 1 位置前方匹配只有一个字符串为 0 (人为规定)
// 4 位置 str2 为 b，前方最大前缀和后缀只有 [a]bc[a]{b} 中的 a 所以为1
// 5 位置 str2 为 c，前方最大前缀和后缀匹配 [ab]c[ab]{c} 中的 ab 长度为2
// 6 位置 str2 为 d，前方最大前缀和后缀匹配 [abc][abc]{d} 中的 abc 长度为3
// 7 位置 str2 为 a，前方最大前缀和后缀匹配 abcabcd{a} 中的无前后缀匹配值，长度为 0
示例
代码
function getNextArray(strArr) {
if (strArr.length === 1) return Array.of(-1) // [-1]
var next/*Number[]*/ = new Array(strArr.length)
next[0] = -1 // 人为规定 next 第0位 -1
next[1] = 0 // 人为规定 next 第1位 0
var i = 2 // 初始位置为 2，因为 2 位置前才有 2 个字符可比较
var cn = 0 // cn 初始匹配为 0, [cn,i-1]{i}
while (i < next.length) {
if (strArr[i - 1] === strArr[cn]) // 匹配上，继续匹配下一位，next 数组当前位置就是 cn 位置前的字符长度，就是 cn 值, 0-6,cn为7，就是7
next[i++] = ++cn
else if (cn > 0) // 没匹配上，cn 跳到前数组匹配位上，也就是当前 next 数组 cn 位置最大前后缀长度的位置，
cn = next[cn]
else // cn 跳到 0 位置 当前的 next[cn] === 0
next[i++] = 0 // 那么 next[i] 位置就为 0 无匹配字符
}
return next
}
使用 next 数组信息加速查找
1 根据 str2 获取到 next 数组
2 str1 和 str2 从第一位字符开始比较
3 当 str1[i1] === str2[i2] 匹配上，i1++, i2++ 按顺序匹配
4 当 next[i2] === -1，str2 与 str1 的第0位没匹配上，str2 的第0位继续跟 str1 下1位比较
var str1 = 'abcdef'
var str2 = 'bcd']
// str2 第0位 b 没匹配上 str1 第0位 a，从下一位比较
5 匹配过程中没有匹配上，则 str2 从当前 next[i2] 处进行推移，考察 str2 最大前缀下一位和 str1 i1 位置，而 str2 最大前缀下一位就是 next 数组当前 i2 的长度值
6 至到 i1 或者 i2 字符撞线，i2 撞线则匹配出位置，i1 撞线则无匹配
代码
function getIndexOf(s1, s2) {
var str1 = s1.spilit('')
var str2 = s2.split('')
var i1 = 0
var i2 = 0
var next = getNextArray(str2) // 根据 str2 生成长度一样的最大匹配前缀后缀的 next 数组
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] === str2[i2])
i1++, i2++
else if (next[i2] === -1)
i1++
else
i2 = next[i2]
}
return i2 === str2.length ? i1 - i2 : -1
}
function getNextArray(strArr) {
if (strArr.length === 1) return Array.of(-1) // [-1]
var next/*Number[]*/ = new Array(strArr.length)
next[0] = -1 // 人为规定 next 第0位 -1
next[1] = 0 // 人为规定 next 第1位 0
var i = 2
var cn = 0
while (i < next.length) {
if (strArr[i - 1] === strArr[cn])
next[i++] = ++cn
else if (cn > 0)
cn = next[cn]
else
next[i++] = 0
}
return next
}
二分查找
在已排序数组查找某数
思路
1 待查找数是 n
2 考察已排序数组 mid 中间位置数是否是 n
3 如果不是，比较 n 与 arr[mid] 大小
4 如果 n > arr[mid] 则从 mid 右边继续查找 新的 arr[mid] 中间位置, 否则就从左边开始查找
5 直到考察到 n === arr[mid] 返回 mid 位置。
代码
/*
* @params {Array} arr1 已排序数组
* @params {Array} arr2
* @return {Array} arr2 中不存在于 arr1 的数
*/
function getNotIncluded(arr1, arr2) {
var res = []
for (var i = 0; i < arr2.length; i++) {
var l = 0;
var r = arr1.length - 1
var has = false
while (l <= r) { // 二分查找核心
var mid = l + ((r - l) >> 1)
if (arr1[mid] === arr2[i]) {
has = true // 找到则跳出
break
}
if (arr1[mid] > arr2[i])
r = mid - 1
if (arr1[mid] < arr2[i])
l = mid + 1
}
if (!has)
res.push(arr2[i])
}
return res
}
