kmp下載

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

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

今天小編就為大家帶來KMP下載的相關資訊。KMP所需GOTO的下一個比較位置，整理出來一個next數組，然后在上面的算法中使用。

定義

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

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

kmp下載

kmp下載圖一

詳細闡述

next數組的理解與計算

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

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

首先擺出next數組

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；

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

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

這樣的話next數組的求解就十分容易了，只需o（n）的復雜度；next[0]必為0，對于求解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下載圖三

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

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