KMP 查找
Knuth-Morris-Pratt字符串查找算法（簡稱為KMP算法）可在一個主文本字符串 str1 內(nèi)查找一個詞 str2 的出現(xiàn)位置慕嚷。
思路
生成 next 數(shù)組
next 數(shù)組是決定了 KMP 算法的下一步匹配的位置信息驮肉。
1 根據(jù)需查找字符串 str2 生成一段 next 數(shù)組信息
2 next 數(shù)組長度與 str2 長度一致
3 next 數(shù)組每一項表達的意思是 str2 當前位置最大匹配前綴與最大匹配后綴的長度信息
最大前綴挫望、最大后綴匹配長度
str2 當前位置前綴后綴的最大匹配字符串長度
考察[aaaaa]{i} i 前的字符
前綴不包括最后一個字符潦刃，后綴不包括第一個字符
var str2 = 'abcabcdabc'
var next = [-1, 0, 0, 0, 1, 2, 3, 0, 1, 2]
// 0 位置前方無匹配為 -1， 1 位置前方匹配只有一個字符串為 0 (人為規(guī)定)
// 4 位置 str2 為 b缘缚，前方最大前綴和后綴只有 [a]bc[a]虽惭 中的 a 所以為1
// 5 位置 str2 為 c，前方最大前綴和后綴匹配 [ab]c[ab]{c} 中的 ab 長度為2
// 6 位置 str2 為 d接谨，前方最大前綴和后綴匹配 [abc][abc]kydstt7 中的 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 // 人為規(guī)定 next 第0位 -1
next[1] = 0 // 人為規(guī)定 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]) // 匹配上兆解，繼續(xù)匹配下一位，next 數(shù)組當前位置就是 cn 位置前的字符長度跑揉，就是 cn 值, 0-6,cn為7锅睛，就是7
next[i++] = ++cn
else if (cn > 0) // 沒匹配上埠巨，cn 跳到前數(shù)組匹配位上，也就是當前 next 數(shù)組 cn 位置最大前后綴長度的位置现拒，
cn = next[cn]
else // cn 跳到 0 位置 當前的 next[cn] === 0
next[i++] = 0 // 那么 next[i] 位置就為 0 無匹配字符
}
return next
}
使用 next 數(shù)組信息加速查找
1 根據(jù) str2 獲取到 next 數(shù)組
2 str1 和 str2 從第一位字符開始比較
3 當 str1[i1] === str2[i2] 匹配上辣垒，i1++, i2++ 按順序匹配
4 當 next[i2] === -1，str2 與 str1 的第0位沒匹配上印蔬，str2 的第0位繼續(xù)跟 str1 下1位比較
var str1 = 'abcdef'
var str2 = 'bcd']
// str2 第0位 b 沒匹配上 str1 第0位 a勋桶，從下一位比較
5 匹配過程中沒有匹配上，則 str2 從當前 next[i2] 處進行推移侥猬，考察 str2 最大前綴下一位和 str1 i1 位置例驹，而 str2 最大前綴下一位就是 next 數(shù)組當前 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) // 根據(jù) str2 生成長度一樣的最大匹配前綴后綴的 next 數(shù)組
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 // 人為規(guī)定 next 第0位 -1
next[1] = 0 // 人為規(guī)定 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
}
二分查找
在已排序數(shù)組查找某數(shù)
思路
1 待查找數(shù)是 n
2 考察已排序數(shù)組 mid 中間位置數(shù)是否是 n
3 如果不是鹃锈，比較 n 與 arr[mid] 大小
4 如果 n > arr[mid] 則從 mid 右邊繼續(xù)查找 新的 arr[mid] 中間位置, 否則就從左邊開始查找
5 直到考察到 n === arr[mid] 返回 mid 位置。
代碼
/*
* @params {Array} arr1 已排序數(shù)組
* @params {Array} arr2
* @return {Array} arr2 中不存在于 arr1 的數(shù)
*/
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
}
