Home >Web Front-end >JS Tutorial >Analysis of JavaScript implementation method based on KMP algorithm_Basic knowledge

Analysis of JavaScript implementation method based on KMP algorithm_Basic knowledge

WBOY
WBOYOriginal
2016-05-16 17:34:501096browse

The core of the algorithm is the partial matching table and the fallback algorithm. The implementation of the partial matching table is as follows:

Copy code The code is as follows :

function kmpGetStrPartMatchValue(str) {
var prefix = [];
var suffix = [];
var partMatch = [];
for(var i =0,j=str.length;i var newStr = str.substring(0,i 1);
if(newStr.length == 1){
partMatch[ i] = 0;
} else {
[k] = newStr.slice(-k-1);
if(prefix[k] == suffix[k]){
partMatch[i] = prefix[k].length;
}
}
if(!partMatch[i]){
partMatch[i] = 0;
}
}
}
prefix.length = 0;
suffix.length = 0;
return partMatch;
}

//demovar t="ABCDABD";

console.log(kmpGetStrPartMatchValue(t));
//output:[0,0,0,0,1,2,0 ]


The fallback algorithm is implemented as follows:



function KMP(sourceStr,targetStr){
var partMatchValue = kmpGetStrPartMatchValue(targetStr);
var result = false;
for(var i=0,j=sourceStr.length;i for(var m=0,n=targetStr.length;m if(str.charAt(m) == sourceStr.charAt(i)){
if(m == targetStr.length-1){
result = true;
break;
} else {
                                                                               ; 🎜>} if (result) {
Break;
}
}
Return result;
}
var s = "bbc abcdabcdabcdabde"; t = "ABCDABD";
console.log(KMP(s,t));
//output: true


Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn