KMP的中心思想，言简意赅两段
1.主串匹配字串之前，先判断子串的每一个位置上，前缀和后缀的最大重复量
2.主串的游标不要回头看，子串动游标，游标回溯到当前字符串的前缀和后缀的最大重复量
function kmpGetStrPartMatchValue(str) {
var prefix = [];
var suffix = [];
var partMatch = [];
for(var i=0;i<str.length;i++){
var newStr = str.substring(0,i+1);
console.log('获得0到i的子串:'+newStr);
if(newStr.length == 1){
partMatch[i] = 0;
console.log('子串长度为1，则匹配位为0:');
} else {
for(var k=0;k<i;k++){
prefix[k] = newStr.slice(0,k+1);
console.log('获得子串前缀:'+prefix[k]);
suffix[k] = newStr.slice(-k-1);
console.log('获得子串后缀:'+suffix[k]);
if(prefix[k] == suffix[k]){
partMatch[i] = prefix[k].length;
console.log('前后缀相等，则匹配位为'+prefix[k]+'的长度:'+partMatch[i]);
}
}
if(!partMatch[i]){
console.log('没有子串匹配，则匹配位为0');
partMatch[i] = 0;
}
}
}
prefix.length = 0;
suffix.length = 0;
return partMatch;
}
function KMP(sourceStr,targetStr){
var partMatchValue = kmpGetStrPartMatchValue(targetStr);
console.log('next数组为'+partMatchValue);
var result = false;
console.log('i负责主串,m负责子串');
var i=0;
for(i=0;i<sourceStr.length;i++){
for(var m=0;m<targetStr.length;m++){
console.log('i='+i+',m='+m);
console.info('子串的第'+m+'位是'+targetStr.charAt(m));
console.info('主串的第'+i+'位是'+sourceStr.charAt(i));
if(targetStr.charAt(m) == sourceStr.charAt(i)){
if(m == targetStr.length-1){
console.info('m==targetStr.length-1,说明匹配');
result = true;
break;
} else {
console.info('m!=targetStr.length-1,说明暂时不匹配,i++');
i++;
}
} else {if(m>0){
console.info('m>0 && partMatchValue[m-1] > 0,说明目前需要对子串的m进行重新定位');
console.info('令m='+(partMatchValue[m-1]-1)+'(next数组为+'+partMatchValue+'第'+(m-1)+'位的数字-1)');
m = partMatchValue[m-1]-1;
} else {
break;
}
}
}
if(result){
break;
}
}
if(result){
return i-targetStr.length+1;
}else{
return -1;
}
}
var s = "AABCDABD";
var t = "ABCDABD";
console.log(KMP(s,t));
打印效果
获得0到i的子串:A
子串长度为1，则匹配位为0:
获得0到i的子串:AB
获得子串前缀:A
获得子串后缀:B
没有子串匹配，则匹配位为0
获得0到i的子串:ABC
获得子串前缀:A
获得子串后缀:C
获得子串前缀:AB
获得子串后缀:BC
没有子串匹配，则匹配位为0
获得0到i的子串:ABCD
获得子串前缀:A
获得子串后缀:D
获得子串前缀:AB
获得子串后缀:CD
获得子串前缀:ABC
获得子串后缀:BCD
没有子串匹配，则匹配位为0
获得0到i的子串:ABCDA
获得子串前缀:A
获得子串后缀:A
前后缀相等，则匹配位为A的长度:1
获得子串前缀:AB
获得子串后缀:DA
获得子串前缀:ABC
获得子串后缀:CDA
获得子串前缀:ABCD
获得子串后缀:BCDA
获得0到i的子串:ABCDAB
获得子串前缀:A
获得子串后缀:B
获得子串前缀:AB
获得子串后缀:AB
前后缀相等，则匹配位为AB的长度:2
获得子串前缀:ABC
获得子串后缀:DAB
获得子串前缀:ABCD
获得子串后缀:CDAB
获得子串前缀:ABCDA
获得子串后缀:BCDAB
获得0到i的子串:ABCDABD
获得子串前缀:A
获得子串后缀:D
获得子串前缀:AB
获得子串后缀:BD
获得子串前缀:ABC
获得子串后缀:ABD
获得子串前缀:ABCD
获得子串后缀:DABD
获得子串前缀:ABCDA
获得子串后缀:CDABD
获得子串前缀:ABCDAB
获得子串后缀:BCDABD
没有子串匹配，则匹配位为0
next数组为0,0,0,0,1,2,0
i负责主串,m负责子串
i=0,m=0
子串的第0位是A
主串的第0位是A
m!=targetStr.length-1,说明暂时不匹配,i++
i=1,m=1
子串的第1位是B
主串的第1位是A
m>0 && partMatchValue[m-1] > 0,说明目前需要对子串的m进行重新定位
令m=-1(next数组为+0,0,0,0,1,2,0第0位的数字-1)
i=1,m=0
子串的第0位是A
主串的第1位是A
m!=targetStr.length-1,说明暂时不匹配,i++
i=2,m=1
子串的第1位是B
主串的第2位是B
m!=targetStr.length-1,说明暂时不匹配,i++
i=3,m=2
子串的第2位是C
主串的第3位是C
m!=targetStr.length-1,说明暂时不匹配,i++
i=4,m=3
子串的第3位是D
主串的第4位是D
m!=targetStr.length-1,说明暂时不匹配,i++
i=5,m=4
子串的第4位是A
主串的第5位是A
m!=targetStr.length-1,说明暂时不匹配,i++
i=6,m=5
子串的第5位是B
主串的第6位是B
m!=targetStr.length-1,说明暂时不匹配,i++
i=7,m=6
子串的第6位是D
主串的第7位是D
m==targetStr.length-1,说明匹配
1
[Finished in 0.1s]
网友评论