talk is cheap，show me the code：
function kmpGetStrPartMatchValue(str) {
var prefix = [];
var suffix = [];
var partMatch = [];
for(var i=0;i<str.length;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;
}
}
}
prefix.length = 0;
suffix.length = 0;
return partMatch;
}
function KMP(sourceStr,targetStr){
var partMatchValue = kmpGetStrPartMatchValue(targetStr);
var result = false;
for(var i=0;i<sourceStr.length;i++){
for(var m=0;m<targetStr.length;m++){
if(targetStr.charAt(m) == sourceStr.charAt(i)){
if(m == targetStr.length-1){
result = i-m;
break;
} else {
i++;
}
} else {
if(m>0 && partMatchValue[m-1] > 0){
m = partMatchValue[m-1]-1;
} else {
break;
}
}
}
if(result){
break;
}
}
return result;
}
var s = "BBC ABCDAB ABCDABDDABDE";
var t = "ABCDABD";
console.log(kmpGetStrPartMatchValue(t));//[0, 0, 0, 0, 1, 2, 0]
console.log(KMP(s,t));//11
