欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(五):經(jīng)典KMP算法

 更新時(shí)間:2015年06月19日 09:49:26   投稿:junjie  
這篇文章主要介紹了JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(五):經(jīng)典KMP算法,本文詳解了KMP算法的方方面在,需要的朋友可以參考下

KMP算法和BM算法

KMP是前綴匹配和BM后綴匹配的經(jīng)典算法,看得出來(lái)前綴匹配和后綴匹配的區(qū)別就僅僅在于比較的順序不同

前綴匹配是指:模式串和母串的比較從左到右,模式串的移動(dòng)也是從 左到右

后綴匹配是指:模式串和母串的的比較從右到左,模式串的移動(dòng)從左到右。

通過(guò)上一章顯而易見(jiàn)BF算法也是屬于前綴的算法,不過(guò)就非常霸蠻的逐個(gè)匹配的效率自然不用提了O(mn),網(wǎng)上蛋疼的KMP是講解很多,基本都是走的高大上路線看的你也是一頭霧水,我試圖用自己的理解用最接地氣的方式描述

KMP

KMP也是一種優(yōu)化版的前綴算法,之所以叫KMP就是Knuth、Morris、Pratt三個(gè)人名的縮寫(xiě),對(duì)比下BF那么KMP的算法的優(yōu)化點(diǎn)就在“每次往后移動(dòng)的距離”它會(huì)動(dòng)態(tài)的調(diào)整每次模式串的移動(dòng)距離,BF是每次都+1,

KMP則不一定

如圖BF與KMP前置算法的區(qū)別對(duì)比

我通過(guò)圖對(duì)比我們發(fā)現(xiàn):

在文本串T中搜索模式串P,在自然匹配第6個(gè)字母c的時(shí)候發(fā)現(xiàn)二等不一致了,那么BF的方法,就是把整個(gè)模式串P移動(dòng)一位,KMP則是移動(dòng)二位.

BF的匹配方法我們是知道的,但是KMP為什么會(huì)移動(dòng)二位,而不是一位或者三位四位呢?

這就上一張圖我們講解下,模式串P在匹配了ababa的時(shí)候都是正確的,當(dāng)?shù)絚的時(shí)候才是錯(cuò)誤,那么KMP算法的想法是:ababa是正確的匹配完成的信息,我們能不能利用這個(gè)信息,不要把"搜索位置"移回已經(jīng)比較過(guò)的位置,繼續(xù)把它向后移,這樣就提高了效率。

那么問(wèn)題來(lái)了, 我怎么知道要移動(dòng)多少個(gè)位置?

這個(gè)偏移的算法KMP的作者們就給我們總結(jié)好了:

復(fù)制代碼 代碼如下:

移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值

偏移算法只跟子串有關(guān)系,沒(méi)文本串沒(méi)毛線關(guān)系,所以這里需要特別注意了

那么我們?cè)趺蠢斫庾哟幸哑ヅ涞淖址麛?shù)與對(duì)應(yīng)的部分匹配值?

已匹配的字符:

復(fù)制代碼 代碼如下:

T : abababaabab
p : ababacb

p中紅色的標(biāo)記就是已經(jīng)匹配的字符,這個(gè)很好理解

部分匹配值:

這個(gè)就是核心的算法了,也是比較難于理解的

假如:

復(fù)制代碼 代碼如下:

T:aaronaabbcc
P:aaronaac

我們可以觀察這個(gè)文本如果我們?cè)谄ヅ鋍的時(shí)候出錯(cuò),我們下一個(gè)移動(dòng)的位置就上個(gè)的結(jié)構(gòu)來(lái)講,移動(dòng)到那里最合理?
復(fù)制代碼 代碼如下:

aaronaabbcc
     aaronaac

那么就是說(shuō):在模式文本內(nèi)部,某一段字符頭尾都一樣,那么自然過(guò)濾的時(shí)候可以跳過(guò)這一段內(nèi)容了,這個(gè)思路也是合理的

 

知道了這個(gè)規(guī)律,那么給出來(lái)的部分匹配表算法如下:

首先,要了解兩個(gè)概念:"前綴"和"后綴"。 "前綴"指除了最后一個(gè)字符以外,一個(gè)字符串的全部頭部組合;"后綴"指除了第一個(gè)字符以外,一個(gè)字符串的全部尾部組合。

"部分匹配值"就是"前綴"和"后綴"的最長(zhǎng)的共有元素的長(zhǎng)度”

我們看看aaronaac的如果是BF匹配的時(shí)候劃分是這樣的

BF的位移: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac

那么KMP的劃分呢?這里就要引入前綴與后綴了

我們先看看KMP部分匹配表的結(jié)果是這樣的:

復(fù)制代碼 代碼如下:

a   a  r  o  n  a  a  c
[0, 1, 0, 0, 0, 1, 2, 0]

肯定是一頭霧水,不急我們分解下,前綴與后綴

復(fù)制代碼 代碼如下:

匹配字符串 :“Aaron”
前綴:A,Aa, Aar ,Aaro
后綴:aron,ron,on,n

移動(dòng)的位置:其實(shí)就是針對(duì)每一個(gè)已匹配的字符做前綴與后綴的對(duì)比是否相等,然后算出共有的長(zhǎng)度

部分匹配表的分解

KMP中的匹配表的算法,其中p表示前綴,n表示后綴,r表示結(jié)果

復(fù)制代碼 代碼如下:

a,         p=>0, n=>0  r = 0

aa,        p=>[a],n=>[a] , r = a.length => 1

aar,       p=>[a,aa], n=>[r,ar]  ,r = 0

aaro,      p=>[a,aa,aar], n=>[o,ra,aro] ,r = 0

aaron      p=>[a,aa,aar,aaro], n=>[n,on,ron,aron] ,r = 0

aarona,    p=>[a,aa,aar,aaro,aaron], n=>[a,na,ona,rona,arona] ,r = a.lenght = 1

aaronaa,   p=>[a,aa,aar,aaro,aaron,aarona], n=>[a,aa,naa,onaa,ronaa,aronaa] ,  r = Math.max(a.length,aa.length) = 2

aaronaac   p=>[a,aa,aar,aaro,aaron,aarona], n=>[c,ac,aac,naac,onaac,ronaac]  r = 0

類似BF算法一下,先分解每一次可能匹配的下標(biāo)的位置先緩存起來(lái),在匹配的時(shí)候通過(guò)這個(gè)《部分匹配表》來(lái)定位需要后移動(dòng)的位數(shù)

所以最后aaronaac的匹配表的結(jié)果 0,1,0,0,0,1,2,0 就是這么來(lái)的

下面將會(huì)實(shí)現(xiàn)JS版的KMP,有2種

KMP實(shí)現(xiàn)(一):緩存匹配表的KMP

KMP實(shí)現(xiàn)(二):動(dòng)態(tài)計(jì)算next的KMP


KMP實(shí)現(xiàn)(一)

匹配表

KMP算法中最重要的就是匹配表,如果不要匹配表那就是BF的實(shí)現(xiàn),加上匹配表就是KMP了

匹配表決定了next下一個(gè)位移的計(jì)數(shù)

針對(duì)上面匹配表的規(guī)律,我們?cè)O(shè)計(jì)一個(gè)kmpGetStrPartMatchValue的方法

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);
      //如果相等就計(jì)算大小,并放入結(jié)果集中
      if (prefix[k] == suffix[k]) {
       partMatch[i] = prefix[k].length;
      }
     }
     if (!partMatch[i]) {
      partMatch[i] = 0;
     }
    }
   }
   return partMatch;
  }

完全按照KMP中的匹配表的算法的實(shí)現(xiàn),通過(guò)str.substring(0, i + 1) 分解a->aa->aar->aaro->aaron->aarona->aaronaa-aaronaac

然后在每一個(gè)分解中通過(guò)前綴后綴算出共有元素的長(zhǎng)度

回退算法

KMP也是前置算法,完全可以把BF那一套搬過(guò)來(lái),唯一修改的地方就是BF回溯的時(shí)候直接是加1,KMP在回溯的時(shí)候我們就通過(guò)匹配表算出這個(gè)next值即可

//子循環(huán)
for (var j = 0; j < searchLength; j++) {
  //如果與主串匹配
  if (searchStr.charAt(j) == sourceStr.charAt(i)) {
    //如果是匹配完成
    if (j == searchLength - 1) {
     result = i - j;
     break;
    } else {
     //如果匹配到了,就繼續(xù)循環(huán),i++是用來(lái)增加主串的下標(biāo)位
     i++;
    }
  } else {
   //在子串的匹配中i是被疊加了
   if (j > 1 && part[j - 1] > 0) {
    i += (i - j - part[j - 1]);
   } else {
    //移動(dòng)一位
    i = (i - j)
   }
   break;
  }
}

紅色標(biāo)記的就是KMP的核心點(diǎn) next的值  = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值

完整的KMP算法

<!doctype html><div id="test2"><div><script type="text/javascript">
 

  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;
     }
    }
   }
   return partMatch;
  }



function KMP(sourceStr, searchStr) {
  //生成匹配表
  var part     = kmpGetStrPartMatchValue(searchStr);
  var sourceLength = sourceStr.length;
  var searchLength = searchStr.length;
  var result;
  var i = 0;
  var j = 0;

  for (; i < sourceStr.length; i++) { //最外層循環(huán),主串

    //子循環(huán)
    for (var j = 0; j < searchLength; j++) {
      //如果與主串匹配
      if (searchStr.charAt(j) == sourceStr.charAt(i)) {
        //如果是匹配完成
        if (j == searchLength - 1) {
         result = i - j;
         break;
        } else {
         //如果匹配到了,就繼續(xù)循環(huán),i++是用來(lái)增加主串的下標(biāo)位
         i++;
        }
      } else {
       //在子串的匹配中i是被疊加了
       if (j > 1 && part[j - 1] > 0) {
        i += (i - j - part[j - 1]);
       } else {
        //移動(dòng)一位
        i = (i - j)
       }
       break;
      }
    }

    if (result || result == 0) {
     break;
    }
  }


  if (result || result == 0) {
   return result
  } else {
   return -1;
  }
}

 var s = "BBC ABCDAB ABCDABCDABDE";
 var t = "ABCDABD";


 show('indexOf',function() {
  return s.indexOf(t)
 })

 show('KMP',function() {
  return KMP(s,t)
 })

 function show(bf_name,fn) {
  var myDate = +new Date()
  var r = fn();
  var div = document.createElement('div')
  div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗時(shí)" + (+new Date() - myDate) + "ms";
   document.getElementById("test2").appendChild(div);
 }


</script></div></div>

KMP(二)

第一種kmp的算法很明顯,是通過(guò)緩存查找匹配表也就是常見(jiàn)的空間換時(shí)間了。那么另一種就是時(shí)時(shí)查找的算法,通過(guò)傳遞一個(gè)具體的完成字符串,算出這個(gè)匹配值出來(lái),原理都一樣

生成緩存表的時(shí)候是整體全部算出來(lái)的,我們現(xiàn)在等于只要挑其中的一條就可以了,那么只要算法定位到當(dāng)然的匹配即可

next算法

function next(str) {
  var prefix = [];
  var suffix = [];
  var partMatch;
  var i = str.length
  var newStr = str.substring(0, i + 1);
  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 = prefix[k].length;
   }
  }
  if (!partMatch) {
   partMatch = 0;
  }
  return partMatch;
}

其實(shí)跟匹配表是一樣的,去掉了循環(huán)直接定位到當(dāng)前已成功匹配的串了

完整的KMP.next算法

<!doctype html><div id="testnext"><div><script type="text/javascript">
 
  function next(str) {
    var prefix = [];
    var suffix = [];
    var partMatch;
    var i = str.length
    var newStr = str.substring(0, i + 1);
    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 = prefix[k].length;
     }
    }
    if (!partMatch) {
     partMatch = 0;
    }
    return partMatch;
  }

  function KMP(sourceStr, searchStr) {
    var sourceLength = sourceStr.length;
    var searchLength = searchStr.length;
    var result;
    var i = 0;
    var j = 0;

    for (; i < sourceStr.length; i++) { //最外層循環(huán),主串

      //子循環(huán)
      for (var j = 0; j < searchLength; j++) {
        //如果與主串匹配
        if (searchStr.charAt(j) == sourceStr.charAt(i)) {
          //如果是匹配完成
          if (j == searchLength - 1) {
           result = i - j;
           break;
          } else {
           //如果匹配到了,就繼續(xù)循環(huán),i++是用來(lái)增加主串的下標(biāo)位
           i++;
          }
        } else {
         if (j > 1) {
          i += i - next(searchStr.slice(0,j));
         } else {
          //移動(dòng)一位
          i = (i - j)
         }
         break;
        }
      }

      if (result || result == 0) {
       break;
      }
    }


    if (result || result == 0) {
     return result
    } else {
     return -1;
    }
  }

 var s = "BBC ABCDAB ABCDABCDABDE";
 var t = "ABCDAB";


  show('indexOf',function() {
   return s.indexOf(t)
  })

  show('KMP.next',function() {
   return KMP(s,t)
  })

  function show(bf_name,fn) {
   var myDate = +new Date()
   var r = fn();
   var div = document.createElement('div')
   div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗時(shí)" + (+new Date() - myDate) + "ms";
    document.getElementById("testnext").appendChild(div);
  }

</script></div></div>

git代碼下載: https://github.com/JsAaron/data_structure

相關(guān)文章

  • JS實(shí)現(xiàn)的tab頁(yè)切換效果完整示例

    JS實(shí)現(xiàn)的tab頁(yè)切換效果完整示例

    這篇文章主要介紹了JS實(shí)現(xiàn)的tab頁(yè)切換效果,涉及javascript基于事件響應(yīng)動(dòng)態(tài)操作頁(yè)面元素屬性相關(guān)操作技巧,需要的朋友可以參考下
    2018-12-12
  • 5個(gè)javascript的數(shù)字格式化函數(shù)分享

    5個(gè)javascript的數(shù)字格式化函數(shù)分享

    Javascript沒(méi)有任何內(nèi)建的格式化函數(shù),這里我們通過(guò)Google收集了5個(gè)javascript的數(shù)字格式化函數(shù),希望對(duì)于大家的web開(kāi)發(fā)能夠帶來(lái)方便
    2011-12-12
  • 前端跨域的幾種解決方式總結(jié)(推薦)

    前端跨域的幾種解決方式總結(jié)(推薦)

    這篇文章主要介紹了前端跨域的幾種解決方式,詳細(xì)介紹了同源策略并同時(shí)給出了跨域的五種解決方案,具體操作步驟大家可查看下文的詳細(xì)講解,感興趣的小伙伴們可以參考一下。
    2017-08-08
  • H5+css3+js搭建帶驗(yàn)證碼的登錄頁(yè)面

    H5+css3+js搭建帶驗(yàn)證碼的登錄頁(yè)面

    這篇文章主要為大家詳細(xì)介紹了H5+css3+js搭建帶驗(yàn)證碼的登錄頁(yè)面,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-10-10
  • json屬性名為什么要雙引號(hào)(個(gè)人猜測(cè))

    json屬性名為什么要雙引號(hào)(個(gè)人猜測(cè))

    json屬性名為什么要雙引號(hào)?更加規(guī)范,利于解析、避免class等關(guān)鍵字引起的不兼容問(wèn)題,需要的朋友可以參考下
    2014-07-07
  • JavaScript重復(fù)元素處理方法分析【統(tǒng)計(jì)個(gè)數(shù)、計(jì)算、去重復(fù)等】

    JavaScript重復(fù)元素處理方法分析【統(tǒng)計(jì)個(gè)數(shù)、計(jì)算、去重復(fù)等】

    這篇文章主要介紹了JavaScript重復(fù)元素處理方法,結(jié)合實(shí)例形式分析了javascript針對(duì)字符串、數(shù)組中重復(fù)元素的個(gè)數(shù)統(tǒng)計(jì),計(jì)算及去重復(fù)等相關(guān)操作技巧,需要的朋友可以參考下
    2017-12-12
  • webpack dll打包重復(fù)問(wèn)題優(yōu)化的解決

    webpack dll打包重復(fù)問(wèn)題優(yōu)化的解決

    在使用dll plugin過(guò)程中出現(xiàn)的一個(gè)包依賴問(wèn)題,這個(gè)問(wèn)題導(dǎo)致打出來(lái)的包會(huì)包含重復(fù)的代碼。這篇文章主要介紹了webpack dll打包重復(fù)問(wèn)題優(yōu)化的解決,感興趣的小伙伴們可以參考一下
    2018-10-10
  • 基于HTML+JavaScript實(shí)現(xiàn)中國(guó)象棋

    基于HTML+JavaScript實(shí)現(xiàn)中國(guó)象棋

    這篇文章主要為大家詳細(xì)介紹了如何利用HTML+CSS+JS實(shí)現(xiàn)中國(guó)象棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-08-08
  • 深入理解Javascript里的依賴注入

    深入理解Javascript里的依賴注入

    我喜歡引用這句話,“程序是對(duì)復(fù)雜性的管理”。計(jì)算機(jī)世界是一個(gè)巨大的抽象建筑群。我們簡(jiǎn)單的包裝一些東西然后發(fā)布新工具,周而復(fù)始?,F(xiàn)在思考下,你所使用的語(yǔ)言包括的一些內(nèi)建的抽象函數(shù)或是低級(jí)操作符。這在JavaScript里是一樣的
    2014-03-03
  • javascript 三種編解碼方式

    javascript 三種編解碼方式

    js對(duì)文字進(jìn)行編碼涉及3個(gè)函數(shù):escape,encodeURI,encodeURIComponent,相應(yīng)3個(gè)解碼函數(shù):unescape,decodeURI,decodeURIComponent
    2010-02-02

最新評(píng)論