function kmpGetStrPartMatchValue(str) { var prefix = []; var suffix = []; var partMatch = []; for (var i = 0, j = str.length; i < j; i++) { var newStr = str.substring(0, i + 1); if (newStr.length == 1) { partMatch[i] = 0; } else { for (var k = 0; k < i; k++) { //前缀 prefix[k] = newStr.slice(0, k + 1); //后缀 suffix[k] = newStr.slice(-k - 1); //如果相等就计算大小,并放入结果集中 if (prefix[k] == suffix[k]) { partMatch[i] = prefix[k].length; } } if (!partMatch[i]) { partMatch[i] = 0; } } } return partMatch; }
完全按照KMP中的匹配表的算法的实现，通过str.substring(0, i + 1) 分解a->aa->aar->aaro->aaron->aarona->aaronaa-aaronaac
然后在每一个分解中通过前缀后缀算出共有元素的长度
回退算法
KMP也是前置算法，完全可以把BF那一套搬过来，唯一修改的地方就是BF回溯的时候直接是加1，KMP在回溯的时候我们就通过匹配表算出这个next值即可
//子循环 for (var j = 0; j < searchLength; j++) { //如果与主串匹配 if (searchStr.charAt(j) == sourceStr.charAt(i)) { //如果是匹配完成 if (j == searchLength - 1) { result = i - j; break; } else { //如果匹配到了，就继续循环，i++是用来增加主串的下标位 i++; } } else { //在子串的匹配中i是被叠加了 if (j > 1 && part[j - 1] > 0) { i += (i - j - part[j - 1]); } else { //移动一位 i = (i - j) } break; } }
红色标记的就是KMP的核心点 next的值 = 已匹配的字符数 - 对应的部分匹配值
完整的KMP算法
<!doctype html><div><div><script type="text/javascript"> function kmpGetStrPartMatchValue(str) { var prefix = []; var suffix = []; var partMatch = []; for (var i = 0, j = str.length; i < j; i++) { var newStr = str.substring(0, i + 1); if (newStr.length == 1) { partMatch[i] = 0; } else { for (var k = 0; k < i; k++) { //取前缀 prefix[k] = newStr.slice(0, k + 1); suffix[k] = newStr.slice(-k - 1); if (prefix[k] == suffix[k]) { partMatch[i] = prefix[k].length; } } if (!partMatch[i]) { partMatch[i] = 0; } } } return partMatch; } function KMP(sourceStr, searchStr) { //生成匹配表 var part = kmpGetStrPartMatchValue(searchStr); var sourceLength = sourceStr.length; var searchLength = searchStr.length; var result; var i = 0; var j = 0; for (; i < sourceStr.length; i++) { //最外层循环，主串 //子循环 for (var j = 0; j < searchLength; j++) { //如果与主串匹配 if (searchStr.charAt(j) == sourceStr.charAt(i)) { //如果是匹配完成 if (j == searchLength - 1) { result = i - j; break; } else { //如果匹配到了，就继续循环，i++是用来增加主串的下标位 i++; } } else { //在子串的匹配中i是被叠加了 if (j > 1 && part[j - 1] > 0) { i += (i - j - part[j - 1]); } else { //移动一位 i = (i - j) } break; } } if (result || result == 0) { break; } } if (result || result == 0) { return result } else { return -1; } } var s = "BBC ABCDAB ABCDABCDABDE"; var t = "ABCDABD"; show('indexOf',function() { return s.indexOf(t) }) show('KMP',function() { return KMP(s,t) }) function show(bf_name,fn) { var myDate = +new Date() var r = fn(); var div = document.createElement('div') div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗时" + (+new Date() - myDate) + "ms"; document.getElementById("test2").appendChild(div); } </script></div></div>
KMP（二）
第一种kmp的算法很明显，是通过缓存查找匹配表也就是常见的空间换时间了。那么另一种就是时时查找的算法，通过传递一个具体的完成字符串，算出这个匹配值出来，原理都一样
生成缓存表的时候是整体全部算出来的，我们现在等于只要挑其中的一条就可以了，那么只要算法定位到当然的匹配即可
next算法