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