數據結構kmp演算法

㈠ 數據結構-串的模式匹配

串的模式匹配就是子串定位操作。給定兩明虧個串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分別是串s和t的長度），在主串s中尋找子串t的過程稱為模式匹配，t稱為模式。如果在s中找到等於t的子串，則稱匹配成功，返回t在s中的首次出現的下標位置；否則匹配失敗，返回-1。

本文介紹三個串模式匹配演算法，分別是簡單回溯演算法（Brute-Force，BF演算法）、KMP演算法、KMP演算法的改進。

從主串s的第0個字元開始，與模式串t的第0個字元開始逐字元比較，不相同時回溯到模式串t的第0個和主串s的第1個字元，重新開始比較。以此類推，直到t的所有字元完成匹配，則匹配成功，否則匹配失敗。

BF演算法速度慢的原因是存在大量不必要的回溯，即在某一趟與t的匹配過程失敗後，需要返回s串開始字元的下一字元重新開始比較，這對於某些模式串t來說是不必要的。例如，若s=12123123132，t=12313，在t與12 12312 3132中加粗子序列進行比較時，在 2 處發生失配，BF演算法接下來將t與121 23123 132、1212 31231 32、12123 12313 2比較。由於t中的231、312與其開始的123並不相同，顯然t與121 23123 132、1212 31231 32的比較是不必要的。

KMP演算法就是利用模式串中與模式串開頭部分子串的重復性來減少重復回溯，實現新一輪比較的直接跳轉。 具體來說，KMP演算法利用一個數組記錄模式串中每一個字元前面有幾個字元與模式串從頭重復，在與s串比較失配時，直接跳轉到重復子串的下一個字元繼續比較，而不用跳轉至模式串t的第0個字元。

演算法步驟： ①計算跳轉數組next。②利用KMP演算法進行模式匹配。

next數組通過遞推計算，即如果當前字元 t[j] 的前一個字元 t[j-1] 與其 next[j-1] 指向的字元 t[next[j-1]] 相同，意味著 t[j] 前的 next[j-1]+1 個字元與從 t[0] 到 t[next[j-1]] 的子串相同，因此 next[j]=next[j-1]+1 ；如果不相同，則遞推至 t[next[j-1]] 的next值指向的字元，與 t[j-1] 比較，直到確認 t[j] 前與 t 串從頭重復的數羨字元數，或者無重復字元標記為薯槐拍 0 。

注意此處的函數返回參數類型為int*，用於 返回一位數組 ，且返回的這個一位數組必須在函數中用static定義。

KMP演算法進行模式匹配時，只需在回溯時將 j 指針賦值為 next[j] 。需要注意的是，若 next[j] 為 -1 ，則意味著 t[j] 前面沒有與 t 從頭重復的字元，且 t[j] 與 s[i] 失配，則 i 和 j 均加 1 。

考慮更特殊的模式串，還能進一步減少不必要的回溯次數。例如，s=111211112，t=11112，按照上述next的計算方式，next={-1,0,1,2,3}。當 i=3, j=3 時失配，此時 s[i]=2, t[j]=1 ，由於 next[j]=2 ，於是 j 跳轉為 2 ，t=11 1 12與s=111 2 11112比較。由於 t[next[j]]=t[j] 也為 1 ，必然與 s[i]=2 不相同，顯然這次回溯也不必要。

總結來說， 當失配的字元與待跳轉的字元相同時，跳轉一步並無意義，可再跳一步 ，即將當前字元置為跳轉後字元的next值。

㈡ KMP是什麼意思

一種由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演算法也是比較著名的模式匹配演算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 發表的一個模式匹配演算法。可以大大避免重復遍歷的情況。

如果使用暴風演算法的話，前面五個字母完全相等，直到第六個字母 "f" 和 "x" 不相等。如下圖：

T = 「abcdex」
j 123456
模式串 abcdex
next[j] 011111

T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123

T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223

T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678

next數組其實就是求解字元串要回溯的位置
假設，主串S= 「abcababca」;模式串T=「abcdex」，由以上分析得出next數組為011111，next數組意味著當主串與模式串不匹配時，都需要從第一個的位置重新比較。

KMP演算法也是有缺陷的，比如主串S=「aaaabcde」,模式串T= 「aaaaax」。next的數組就是012345；

當開始匹配時，當i= 5，j = 5時，我們發現字元"b"與字元「a」不相等，如上圖，j = next[5] = 4;

由於T串的第二、三、四、五位置的字元都與首位「a」相等，那麼可以用首位next[1]的值去取代與它相等的後續字元的next[j],那麼next數組為{0,0,0,0,0,5};

在求解nextVal數組的5種情況

㈣ KMP是什麼意思

kmp演算法是一種改進的字元串匹配演算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP演算法）。KMP演算法的關鍵是根據給定的模式串W1,m,定義一個next函數。next函數包含了模式串本身局部匹配的信息。
完全掌握KMP演算法思想
學過數據結構的人，都對KMP演算法印象頗深。

㈤ 演算法-KMP

大一下參加學校ACM預備隊集訓的時候首次接觸KMP演算法，當時看了很多介紹文章，仍然不是很理解其實質，只是簡單地套模板AC題目，待大二數據結構與演算法課堂上再聽老師介紹一次，才恍然大悟其實KMP也就是那麼回事嘛。但當初為啥看那麼多文章都沒弄明白呢？正巧最近和朋友聊天時他告訴我他對KMP不是很理解，於是打算自己寫一篇文章，鞏固自己對KMP的認識，也希望能夠幫助更多朋友理解KMP。
在開始之前，需要知曉的概念：

前綴：以原串串頭為自身串頭的子串，如 的前綴有：
後綴：以原串串尾為自身串尾的子串，如 的後綴有：

注意：字元串前後綴都不包括該串本身

給你一個文本串T(Text String)

再給你一個模式串P(Pattern String)

問該模式串是否在文本串中，怎麼找？

一開始只好分別從文本串與模式串的串頭開始逐字母比較

二者相同，再比較T串與P串的下一位

如此反復

如果一直這么順利，兩串對應位置的字元總相同，待P串中最後一個字元也匹配完畢，說明該模式串在文本串中存在，耶( •̀ ω •́ )y超開心，查找結束。但，大多數匹配過程不會如此順利，在該例中，當匹配進行至

很明顯，失配了。現在怎麼辦？按樸素思想，將P串相對T串整體右移一位，重新開始匹配，即

但這種演算法效率無疑是十分低下的。設T串長度N，P串長度M，則樸素演算法時間復雜度為O(MN)

已知的重要信息並沒有被使用——已匹配的字元串前綴

在上例中，當P串最後一個字元匹配失敗時，其已有包含七個字元的 前綴子串S 匹配成功

完全可以利用前綴子串S做點什麼。觀察到在S串

中，有相同前後綴，即下圖藍色部分

而S串各字元又與T串中對應字元相同，即有

當失配發生後，直接將P串右移四位使S串藍色後綴部分對齊T串中藍色前綴部分

從圖中紅框部分繼續嘗試匹配，發現再次失配。這次，已匹配成功的前綴串S為

而在該串中沒有相同的前後綴，只能將P串串頭移至失配處進行比較

再次失配。此時前綴串S為空串，只好如樸素演算法般將P串整體右移一位，重新開始比較

匹配成功。於是又按照之前的步驟往下匹配，直至再次失配或匹配成功

後續步驟同上，不再贅述

上述示例已展現，KMP演算法的精髓在於對已匹配成功的前綴串S的利用

在樸素演算法中，匹配失敗了，T串待匹配字元會回溯

T串原本已匹配至T[7] = 'X'，但是因為失配，需回溯到T[1] = 'b'重新開始匹配

而在KMP演算法中，若P[M]與T[K]匹配失敗，K不會回溯。既然匹配過程是從T[0]開始逐漸向右進行的，至T[K]失配發生時，T[0]至T[K-1]早已匹配過，何必再回溯過去重復匹配呢？於是乎，就如問題引入部分展示般

每當失配發生，我們總是去關注P串中已匹配成功的前綴串S

因為該前綴串是匹配成功的，說明在T串中必定存在與該前綴串相同的子串，記為S'

若S串中存在相同前後綴

則S'串必然也存在此相同前後綴

所以只需將P串右移四位，使得S串的該相同前綴對齊S'串的該相同後綴

再嘗試比較T[7]與P[3]

至於T[7]與P[3]是否能夠匹配另說（當然，本例中一看就知道沒匹配上），但通過對前綴串S的利用，成功省去了P串右移一位、兩位和三位後的無效匹配

繼續深入思考，給定一個具體的P串，其第N位的前綴串S內容是固定的，則S是否存在相同前後綴、相同前後綴的長度與內容也是確定的。換言之，對於一個具體的P串，當其與給定T串匹配至P[N]失配，P串應右移幾位再次與T串進行匹配也是確定的。我們完全可以使用一個數組記錄當P[N]失配後，應當使用N之前的哪一位再來與T串進行匹配，以此提高匹配效率，記該數組為Next數組

定義Next[i] = j表示當P串中第i位失配後，跳轉至P串第j位再次嘗試匹配

還是以之前的P串為例，它的Next數組求出來應為

取下標5為例，其前綴串為

最長相同前後綴為

若P[5]失配，應跳轉至P[1]再次嘗試匹配（最長相同前綴對應P[0]，則取其後一位P[1]，若存在多位，則取最後一位的下一位），P[5]的前一個字元P[4]對應字元'a'，而P[1]前一個字元P[0]同對應字元'a'，保證了P[1]之前字元與T串中對應字元保持匹配。所以Next[5] = 1，其餘下標對應Next數組值同如此求。

特別地，規定Next[0] = -1。而對於除下標0外的任意下標N，Next[N]的含義是 前N-1個已匹配成功的字元構成的前綴串S中，最長相同前後綴長度。 所以若在下標為N處匹配失敗了，則應前往Next[N]所對應的下標處匹配。

具體地，以下圖所示為例，P[6]與T[6]失配

而Next[6] = 2，所以使用P[2]再次嘗試與T[6]進行匹配

當求出P串Next數組後，便可快速進行與T串的匹配

現在問題只剩下如何求Next數組，注意到Next數組既然只與P串本身相關，與文本串T無關，故令P串與自身匹配即可求得

考慮字元串

其Next數組應為

令其與給定文本串相匹配

當匹配進行至

失配，於是跳轉至P[Next[3]] = P[1]處再次嘗試匹配

再度失配，也必然失配

問題在於不該出現P[N] =P[Next[N]]

若P[N] =P[Next[N]]，則P[N]失配後使用P[Next[N]]再次嘗試匹配，由於P[N] =P[Next[N]]，P[N]匹配失敗，P[Next[N]]必然也失敗

因此，若出現P[N] =P[Next[N]]情況，則令Next[N]=Next[Next[N]]

本例中該字元串新Next數組為

當匹配進行至

失配，於是跳轉至P[Next[3]] = P[0]處再次嘗試匹配

省去了之前跳轉至P[1]處的無效匹配

設T串長度M，P串長度N，由於KMP演算法不會回溯，分析易知時間復雜度為O(m+n)

對於P[N]，若其前綴串S含相同前後綴F，且F長度為n（n>1），Next[N]可以取1至n中任意值，為最大化匹配效率考慮，總是取最大相同前後綴以提高效率，節省時間

㈥ kmp演算法難嗎是什麼級別

KMP演算法是我們數據結構串中最難也是最重要的演算法。難是因為KMP演算法的代碼很優美簡潔干練，但裡麵包含著非常深的思維。真正理解代碼的人可以說對KMP演算法的了解已經相當深入了。而且這個演算法的不少東西的確不容易講懂，很多正規的書本把概念一擺出直接勸退無數人。這篇文章將盡量以最詳細的方式配圖介紹KMP演算法及其改進。文章的開始我先對KMP演算法的三位創始人Knuth,Morris,Pratt致敬，懂得這個演算法的流程後你真的不得不佩服他們的聰明才智。