function next(str) { var prefix = []; var suffix = []; var partMatch; var i = str.length var newStr = str.substring(0, i + 1); 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 = prefix[k].length; } } if (!partMatch) { partMatch = 0; } return partMatch; }
其实跟匹配表是一样的，去掉了循环直接定位到当前已成功匹配的串了
完整的KMP.next算法
<!doctype html><div><div><script type="text/javascript"> function next(str) { var prefix = []; var suffix = []; var partMatch; var i = str.length var newStr = str.substring(0, i + 1); 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 = prefix[k].length; } } if (!partMatch) { partMatch = 0; } return partMatch; } function KMP(sourceStr, 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 { if (j > 1) { i += i - next(searchStr.slice(0,j)); } 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 = "ABCDAB"; show('indexOf',function() { return s.indexOf(t) }) show('KMP.next',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("testnext").appendChild(div); } </script></div></div>
git代码下载: https://github.com/JsAaron/data_structure
您可能感兴趣的文章: