kmp下載

時(shí)間：2019-09-25 11:40:07 作者：無名瀏覽量：60

KMPlayer 4.2.2.28 中文版
大小：36.14 MB
日期：2019/9/25 11:40:07
環(huán)境：WinXP, Win7, Win8, Win10, WinAll

今天小編就為大家?guī)鞬MP下載的相關(guān)資訊。KMP所需GOTO的下一個(gè)比較位置，整理出來一個(gè)next數(shù)組，然后在上面的算法中使用。

定義

一種由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人設(shè)計(jì)的線性時(shí)間字符串匹配算法。這個(gè)算法不用計(jì)算變遷函數(shù)δ，匹配時(shí)間為Θ（n），只用到輔助函數(shù)π[1，m]，它是在Θ（m）時(shí)間內(nèi)，根據(jù)模式預(yù)先計(jì)算出來的。

數(shù)組π使得我們可以按需要，“現(xiàn)場(chǎng)”有效的計(jì)算（在平攤意義上來說）變遷函數(shù)δ。粗略地說，對(duì)任意狀態(tài)q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了與a無關(guān)但在計(jì)算δ（q，a）時(shí)需要的信息。由于數(shù)組π只有m個(gè)元素，而δ有Θ（m∣Σ∣）個(gè)值，所以通過預(yù)先計(jì)算π而不是δ，使得時(shí)間減少了一個(gè)Σ因子。

kmp下載

kmp下載圖一

詳細(xì)闡述

next數(shù)組的理解與計(jì)算

首先聲明在不同的地方對(duì)next數(shù)組的定義和計(jì)算有所不同，為了避免混淆，在此僅介紹一種。

next數(shù)組是對(duì)于模式字符串也就是需要被匹配字符串其中的每一個(gè)字母而言，為了在匹配時(shí)避免重復(fù)判斷而存在，下面通過一個(gè)實(shí)例來介紹next數(shù)組的意義和具體用法。

首先擺出next數(shù)組

kmp下載

kmp下載圖二

a 匹配串：b a b a b b；

0 0 1 2 3 1；

列如 s原串：b a b a b a b c b a b a b a b a b b；

a匹配串：b a b a b b；

先按暴力匹配可以得到如下

原串：b a b a b a bcb a b a b a b a b b；

匹配串 b a bab b；

在如圖黑色字母處出現(xiàn)不匹配，如果繼續(xù)暴力，則會(huì)將匹配串向后移一位，然后再重新將匹配串的指針指向首位重新開始逐個(gè)匹配。但現(xiàn)在思考一下，我已經(jīng)匹配了過了前三個(gè)字符了，可不可以合理地利用已知的條件呢？

next數(shù)組就起到了運(yùn)用已知條件的作用。如next[2]=1（從0開始），代表從匹配串隊(duì)首開始向后走1（包括此點(diǎn)）與從a[2]開始向前走1的字符串完全相同。如next[3]=2，代表a[0]，a[1]所組成的字符串與a[2]a[3]組成的完全相同。next[n]就代表n滿足上述條件的長(zhǎng)度。

這樣的話next數(shù)組的求解就十分容易了，只需o（n）的復(fù)雜度；next[0]必為0，對(duì)于求解next[n]，采用遞推思想，如果next[n]=k;(k>0)則必須next[n-1]=k-1;如果next[n-1]=0;則看next[n]是否等于next[0]。如等于則next[n]=1。

kmp下載

kmp下載圖三

接下來就是實(shí)現(xiàn)時(shí)next數(shù)組的現(xiàn)實(shí)作用了，如上圖，設(shè)原串的指針為i，匹配串的指針為j。當(dāng)匹配到a[3]失敗時(shí)，要注意因?yàn)閺腶[j]即a[3]開始向前走next[j-1]，即1與從隊(duì)首開始向后走next[j-1]的字符是相同的，所以j回到next[j-1]，即a[1]的位置，而i指針不變，再進(jìn)行比較。這樣就能高效地進(jìn)行匹配。

結(jié)合圖像來看，如右下圖加黑的B與A部分就是匹配失敗時(shí)next[j-1]的值代表B部分與A部分完全相同，所以直接跳過這部分，直接將j指針移到A部分的后一位處，即next[j-1]處。