アルゴリズムの核心は、部分一致テーブルとフォールバック アルゴリズムです。部分一致テーブルの実装は次のとおりです。
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;
}
//デモvar t="ABCDABD";console.log(kmpGetStrPartMatchValue(t));
//output:[0,0,0,0,1,2,0 ]
フォールバック アルゴリズムは次のように実装されます:
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 (結果) {
ブレーク;
}
}
結果を返す;
}
var s = "bbcabcdabcdabde";
console.log(KMP( s,t));
//出力: true
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
