算法的核心是部分匹配表和回退算法,部分匹配表的实现如下:
复制代码 代码如下:
function kmpGetStrPartMatchValue(str) {
var prefix = [];
var suffix = [];
var partMatch = [];
for(var i=0,j=str.length;i<j;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;
}
//demo
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<j;i++){
for(var m=0,n=targetStr.length;m<n;m++){
if(str.charAt(m) == sourceStr.charAt(i)){
if(m == targetStr.length-1){
result = true;
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 ABCDABCDABDE";
var t = "ABCDABD";
console.log(KMP(s,t));
//output: true
KMP算法,JavaScript
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
更新日志
- 纪钧瀚《钢琴阅读时光 雨中书店聆听轻音乐》[FLAC/分轨][399.62MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[320K/MP3][87.4MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[FLAC/分轨][184.94MB]
- 陈慧娴.2018-Priscilla-Ism演唱会3CD(2024环球红馆40复刻系列)【环球】【WAV+CUE】
- 郑秀文.1999-我应该得到(国)【华纳】【WAV+CUE】
- 陈家慧.2011-钢琴酒吧2CD【龙吟唱片】【WAV+CUE】
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[320K/MP3][45.01MB]
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[FLAC/分轨][109.13MB]
- 赞多《序章》[320K/MP3][45.54MB]
- 许巍.2004-每一刻都是崭新的【步升大风】【WAV+CUE】
- 群星.2024-四方馆影视原声带【韶愔音乐】【FLAC分轨】
- 陈雷.1997-安锁咧【金圆唱片】【WAV+CUE】
- 关淑怡.2013-MY.FAVORITE.SK.3CD【环球】【WAV+CUE】
- Sweety.2006-花言乔语【丰华】【WAV+CUE】
- 李恕权.2003-回·20年全精选2CD【SONY】【WAV+CUE】