快捷導(dǎo)航

基于KMP算法JavaScript的實(shí)現(xiàn)方法分析

更新時(shí)間：2013年05月03日 12:01:40 作者：

本篇文章介紹了，基于KMP算法JavaScript的實(shí)現(xiàn)方法分析。需要的朋友參考下

算法的核心是部分匹配表和回退算法，部分匹配表的實(shí)現(xiàn)如下：

//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過程中發(fā)現(xiàn)結(jié)果集有數(shù)據(jù)，我如何通過變量獲取呢
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)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(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
JavascriptES6新特性之map和reduce詳解
這篇文章主要為大家詳細(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
淺談ECMAScript6新特性之let、const
下面小編就為大家?guī)?lái)一篇淺談ECMAScript6新特性之let、const。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧
2017-08-08
Javascript開發(fā)之三數(shù)組對(duì)象實(shí)例介紹
Javascript開發(fā)之三組數(shù)對(duì)象詳細(xì)介紹，需要的朋友可以參考下
2012-11-11
JS保存和刪除cookie操作判斷cookie是否存在
本文內(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)樱唧w操作步驟大家可查看下文的詳細(xì)講解，感興趣的小伙伴們可以參考一下。
2017-08-08