基于KMP算法JavaScript的實(shí)現(xiàn)方法分析
更新時(shí)間：2013年05月03日 12:01:40 作者：
本篇文章介紹了，基于KMP算法JavaScript的實(shí)現(xiàn)方法分析。需要的朋友參考下
算法的核心是部分匹配表和回退算法，部分匹配表的實(shí)現(xiàn)如下：
復(fù)制代碼 代碼如下:
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]
回退算法實(shí)現(xiàn)如下：
復(fù)制代碼 代碼如下:
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
相關(guān)文章
如何獲取JQUERY AJAX返回的JSON結(jié)果集實(shí)現(xiàn)代碼
我寫了個(gè)方法,用于查詢結(jié)果,但debug過(guò)程中發(fā)現(xiàn)結(jié)果集有數(shù)據(jù)，我如何通過(guò)變量獲取呢2012-12-12
淺談js和css內(nèi)聯(lián)外聯(lián)注意事項(xiàng)
下面小編就為大家?guī)?lái)一篇淺談js和css內(nèi)聯(lián)外聯(lián)注意事項(xiàng)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-06-06
輕松學(xué)習(xí)JavaScript函數(shù)中的 Rest 參數(shù)
ES6 引入 rest 參數(shù)用于獲取函數(shù)的多余參數(shù)，這樣就不需要使用arguments對(duì)象了。rest 參數(shù)搭配的變量是一個(gè)數(shù)組，該變量將多余的參數(shù)放入數(shù)組中。下面我們來(lái)詳細(xì)了解一下吧2019-05-05
這篇文章主要為大家詳細(xì)介紹了ES6的新特性之map和reduce，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
Javascript 按位左移運(yùn)算符使用介紹(<<)
這篇文章主要介紹了Javascript 按位左移運(yùn)算符 (<<) 將表達(dá)式數(shù)字轉(zhuǎn)換成二進(jìn)制，之后向左移表達(dá)式的位的相關(guān)資料,需要的朋友可以參考下2014-02-02
De facto standard 世界上不可思議的事實(shí)標(biāo)準(zhǔn)
前些天IEBlog中提到實(shí)現(xiàn)互通并不是只靠標(biāo)準(zhǔn)就行，其中舉出了一些關(guān)于事實(shí)上的標(biāo)準(zhǔn)的考慮——所謂“事實(shí)上的標(biāo)準(zhǔn)”，也就是并非標(biāo)準(zhǔn)，但大家都遵循著它去做事情的那么一種東西。2010-08-08
下面小編就為大家?guī)?lái)一篇淺談ECMAScript6新特性之let、const。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-08-08
Javascript開(kāi)發(fā)之三數(shù)組對(duì)象實(shí)例介紹
Javascript開(kāi)發(fā)之三組數(shù)對(duì)象詳細(xì)介紹，需要的朋友可以參考下2012-11-11
本文內(nèi)容講的是:JS保存和刪除cookie操作,判斷cookie是否存在的方法2013-11-11
原生JavaScript來(lái)實(shí)現(xiàn)對(duì)dom元素class的操作方法(推薦)
這篇文章主要介紹了原生JavaScript來(lái)實(shí)現(xiàn)對(duì)dom元素class的操作方法,提供了代碼toggleClass的測(cè)試?yán)?，具體操作步驟大家可查看下文的詳細(xì)講解，感興趣的小伙伴們可以參考一下。2017-08-08