KMP經典算法與變形的應用（字符串parttern匹配問題）

?1. 問題描述

求主串字符串a是否含有模式串字符串parttern b，也就是匹配問題經典KMP算法是計算next[j]數組，然后每次移動若干位而不是暴力求解的每次移動到partern的首位來比較。

暴力求解的算法很明顯時間復雜度是O（m*n），而KMP（三個發明者的首字母）算法 的時間復雜度是O（m+n），為什么時間復雜度是O（m+n），以及KMP算法的

關鍵點next[]數組的求解的精髓——相等的最長前綴后綴串長度數組的求解在下面進行介紹。

最后還會介紹一下KMP的next數組的變形（有些情形下將會提速）。

2.暴力求解BF

主串每次移動一個位置，每次都與模式串partern進行比較，當遇到不相同元素的時候進行break結束當前循環，然后主串移動到下一個位置.....不用多說

1 def bf(s, partern): 2 start = 0 3 while start <= (len(s) - len(partern)): 4 partern_index = 0 5 for i in xrange(start, start+len(partern)): 6 if partern[partern_index] != s[i]: 7 break 8 elif partern_index == (len(partern)-1): 9 return start 10 partern_index += 1 11 start += 1 12 return -1

?

3. KMP經典算法

核心思想：

　　在比較的過程中，當遇到a[i] != b[j]的時候并不是將索引 i 移動到當前比較開始處的下一位而是移動模式串！！！這就是主串不回溯！

　　那么把模式串移動到哪里？？這就是接下來分析的next[]

以下圖片來源于july課程，不再標注

目的就是黃色元素和綠色元素不相等時候，將模式串移動若干位使得BD串=AC串，是不是節省了很多很多比較

3.1 next[]數組求解

? ? s? ? ? =? ?'abababcdgababcabcdcfabcabbbaabccc'
partern =? ?'abcabcdcfabcabbb'

?求解模式串parttern的每一個元素的最大相等的前綴串和后綴串

思想：如果p[k] == p[j]，那么令next[j+1] = next[j]+1

　　? ?如果p[k] != p[j]，那么令h = next[k];比較p[h] 與p[j]的相等關系

? ? ? ? ? 重復此過程，看起來像是從后向前的遞歸實際上求解過程是從前向后的一個求解

還是舉個例子比較通俗易懂：partern =? ?'abcabcdcfabcabbb'

next[0] = -1

指針移動到b的位置時，很顯然a自己沒有所謂的前綴后綴，所以next[1] =0

指針移動到c..............，顯然ab沒有相等的前綴后綴..................next[2] = 0

.................a.........................abc.................................................next[3]=0

.................b.........................abca的前綴有a ab abc abca，后綴有a c bca有一個相同的就是a，長度是1，所以next[4] =1

以此類推

最終得到：

next=[-1, 0, 0, 0, 1, 2, 3, 0, 0, 0, 1, 2, 3, 4, 5, 0]

1 def get_next(partern): 2 nex = [-1] * len(partern) 3 index = 0 4 k = -1 5 while (index < len(partern) - 1): 6 if k == -1 or partern[index] == partern[k]: 7 index += 1 8 k += 1 9 nex[index] = k 10 else: 11 k = nex[k] 12 return nex

接下來就可以進行kmp的求解了。

3.2 KMP算法代碼

?一句話：與暴力求解的思維一樣，只不過主串不回溯，根據next[]移動模式串。

1 def kmp(s, partern): 2 nex = get_next(partern) 3 index = 0 4 start = 0 5 while start < (len(partern)-1): 6 if start == -1: 7 index += 1 8 start = 0 9 continue 10 if s[index] == partern[start]: 11 index += 1 12 start += 1 13 else: 14 start = nex[start] 15 return index - start s = 'adgababcabcdcfabcabbbaabccc'
parttern = 'abcabcdcfabcabbb'
結果是 5

3.3 KMP算法時間復雜度解釋

?為什么KMP的算法時間復雜度是O（m+n）

首先在求解next[]數組的時候是遍歷的求，因此式m，關于遞歸問題上面已經說過了，真正求解是從前向后，因此前面的next值已經求出來了，所以可以忽略

在執行KMP的時候實際上也是遍歷，長度是n，過程中不回溯，因此比較的次數仍然是n（平均），因此是O（m+n）

4.KMP算法變形

?現在考慮這樣一個問題，當s[i] == p[j]的時候i++ j++，當出現s[i] != p[j]的時候會根據next[]移動p的索引，假如說 j=10,next[j] = 2,同時p[10] == p[2]這種情況，是不是做了一次無用功，因為s[i] != p[j]已經確定了，不然不可能移動p，換句話說s[i] != p[2]所以本次移動是無用功，還得繼續移動。看下圖

因此在求解KMP的時候加上一個判斷，如果p在j位置的元素值與要移動到k的位置的元素值是相同的，那么就移動到p[next[next[j]]]? 而不是p[next[j]]

1 def kmp2(s, partern): 2 nex = get_next(partern) 3 index = 0 4 start = 0 5 while start < (len(partern) - 1): 6 if start == -1: 7 index += 1 8 start = 0 9 continue 10 if s[index] == partern[start]: 11 index += 1 12 start += 1 13 else: 14 if parttern[start] == parttern[nex[start]]: 15 start = nex[nex[start]] 16 start = nex[start] 17 return index - start

結果仍然是5

同時都調用kmp(s, parttern) 和kmp2(s, parttern)可以count一下循環的次數來比較兩者的速度。

參考鏈接：

http://www.cnblogs.com/c-cloud/p/3224788.html

https://www.cnblogs.com/yjiyjige/p/3263858.html

等

有任何疑問請留言或者發送至郵箱397585361@qq.com

轉載于:https://www.cnblogs.com/sunll9201/p/9998176.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的KMP经典算法与变形的应用（字符串parttern匹配问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。