KMP 알고리즘 기반 JavaScript 구현 방법 분석_기본지식

알고리즘의 핵심은 부분 매칭 테이블이며, 폴백 알고리즘은 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

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] == 접미사 [k]){
partMatch[i] = 접두사[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 ]


fallback 알고리즘은 다음과 같이 구현됩니다.

코드 복사 코드는 다음과 같습니다.

함수 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){
결과 = true;
중단;
} else {
                                                                    🎜>} if (결과) {
중단;
}
}
결과 반환
}
var s = "bbc abcdabcdabde";
console.log(KMP( s,t));
//출력: true