普通的模式匹配演算法(BF演算法)
子串的定位操作通常稱為模式匹配演算法
假設有一個需求，需要我們從串“a b a b c a b c a c b a b"中，尋找內容為“a b c a c”的子串，
此時，稱“a b a b c a b c a c b a b"為主串S，“a b c a c”為模式串T，
很容易想到，通過遍歷主串S，與模式串T的首字母逐一比對，當主串S中的某一元素i與模式串T首字符j相同，則將主串S中第i+1個字符與模式串T的j+1個字符繼續匹配，若匹配成功，則繼續將主串S中的第i+2個字符與模式串T中的第j+2個字符進行比對，若匹配失敗，則將主串S的第i+1個字符與模式串的第j個字符重新比對....
將上述文字轉化為影像如下：
按照影片的顯示效果很容易理解BF模式匹配演算法，
通過分析可以得出，每次匹配失敗之后，i的指向又將回到主串S的i-j+2位置
通過C語言偽代碼的方式實作：
若將主串S的長度看作m，將模式串T的長度看作n
則該代碼的時間復雜度為O(m+n)
BF演算法確實實作了模式匹配的目的，但同時也有較大的缺陷
模式匹配改進演算法(KMP演算法)的引出
假設目前有這樣一個主串S與模式串T
主串S：
模式串T：
比對程序：
顯而易見，使用BF模式匹配演算法，一旦遇到主串S元素與模式串T高度重合，但鮮有不同，
此種演算法將進行大量重復的“主串S回退”，如此一來，時間復雜度將達到
O(m*n)
而后，D.E.Knuth與V.R.Pratt和J.H.Morris發現了一套模式匹配的改進演算法，根據他們的名字的字母，該演算法被命名為：
KMP演算法
KMP演算法
KMP演算法基本概念
KMP演算法可以在時間復雜度為O(m+n)的時間數量級上完成模式匹配操作，
其不同點在于，在匹配失敗之后，不需要回溯i指標
而是利用已經“部分匹配”的結果，將模式串T向右滑動盡可能遠的距離
(KMP演算法比對程序1)
(KMP演算法比對程序2)
(KMP演算法比對程序3)
從該描述中我們提取出要使用KMP演算法最核心的三個問題：1.滑動的條件 2.滑動的模式 3.滑動距離k的求解
滑動的條件
這部分我們探究當發生“失配”后，主串S中的i應該與模式串T中的第幾個字符(這里用K指代)繼續進行比較，
在什么條件下我們可以將視窗進行“滑動”？或者說，怎樣才叫發生了“部分匹配”？
這里給出嚴蔚敏版的《資料結構》中，對于“部分匹配”條件的定義(模式串為p，主串為s)：
①
②
\[p_{j-k+1}p_{j-k+2}...p_{j-1} = s_{i-k+1}s_{i-k+2}...s_{i-1} \]③
\[p_1p_2...p_{k-1} = p_{j-k+1}p_{j-k+2}...p_{j-1} \]剛看到這三個公式的時候，有點懵，但仔細比對之后可以發現
公式①說明：模式串p從頭開始的子串與后面某段已發生“部分匹配”的主串s的子串q相同
公式②說明：模式串p在除開頭以外，有一段子串與剛才的子串q發生了“部分匹配”
公式③說明：如果滿足上述兩個條件，則可以得出模式串p中有兩端相同的子串
如果滿足以上三個條件(滿足前兩個條件則第三個必定滿足),則可以快速“滑動k個位置”來進行KMP模式匹配
滑動的模式
明確了前提條件之后，我們建立應該next[j]來保存每次比對結束后的K值
約定：
| next[j] | 條件 | 結果 |
|---|---|---|
| 0 | 當j等于1 | 將i向后移動一位 |
| k | 取Kmax，1<k<j 且 滿足條件③ | 將模式串的第k位與當前i對齊 |
| 1 | 其他情況 | 將模式串的第1位與當前i對齊 |
反映成代碼形式：
滑動距離K的求解
由
\[p_1p_2...p_{k-1} = p_{j-k+1}p_{j-k+2}...p_{j-1} \]- 可知next[j]僅與模式串有關而與主串無關
這里是整個KMP演算法的核心部分，在我反反復復看幾十遍嚴蔚敏版的《資料結構》之后，我終于理清了整個求解滑動距離的方法，
整個演算法分為兩個情況：
以及
\[p_k ≠ p_j \] 若滿足第一種情況，有next[j+1] = next[j] + 1;
若滿足第二種情況，則又分為兩種情況
- 設K' = next[k],當P[K'] = P[j] 時，有
next[j+1] = next[k] + 1; - 如果一直移動K'到j = 1時，還不能找到對應的P[K'] = P[j],那么直接有
next[j+1] = 1;
在展開講求next[j]的演算法之前，必須要明確的一點是：
- k，j，k'，j+1分別代表串中的哪些位置
在這里給出明確定義：
- j+1就是你需要求k值的模式串位置
- j就是當前需要求出K值的字符的前一個字符
- k-1就是“已匹配”的前綴的最后一個字符
- k就是“已匹配”的前綴的最后一個字符的后一個字符
注意
- 前綴一定要包含第1個字符
- 后綴一定要包含希望求得K的字符的前一個字符
如圖所示，如果我們要求得串中第5個字符的K值，假設前四個字符K值均已經求得，設我們的目標字符指標為j+1
又有第1個‘a’與第3個‘a'匹配，所以他們分別為k-1和j-1
因此第2個字符為k，第4個字符為j，
- 重點來了
讓我們拋出一個例子，來理解next[j]的求法
假設我們已知j=1，2，3，4的next[j]值分別為：0，1，1，2
由于k-1和j-1已經”匹配“，則滿足前置匹配條件，我們來比較pk和pj的內容，
pk = b，pj = a；
可見它們并不相等，因此k指向的b會甩鍋給“next[k]”字符，而next[k] = 1，也就是串的第一個字符‘a'
第一個字符‘a'成功與第j個字符‘a'相匹配，因此依照我們定義的的pk ≠ pj的第一種情況可以得到
next[j+1] = next[k] + 1 = 2;
由此，我們可以通過之前定義的方式來確定所有的next[j]的值，下面給出串'abaabcac'的所有next[j]的值：
希望讀者能拿起筆，從next[2]開始，計算到next[8]
相信計算完上表格的讀者，已經對next[j]的計算方法有了更加深刻的理解
在這里我也分享出自己總結的口訣：
- k，j相等，直接加1
- k，j不等，層層甩鍋
- 甩鍋失敗，直接賦1
- 甩鍋成功，老板加1
釋義：
- pk = pj：next[j+1] = next[j] + 1;
- pk ≠ pj: 甩鍋
- p[k'] = pj:next[j+1] = next[k] + 1;
- p[k'] ≠ pj:next[j+1] = 1 or 繼續向next[k']甩鍋，
接下來給出代碼實作求next[j]：
KMP演算法的改進
通過分析代碼我們可以發現，當模式串元素有多個重復元素：
他們的next[j]為：0，1，2，3，4
因此在比對時將出現i不動，j從呼叫next[j]3次的情況，
在這種情況下，我們可以讓j=1，2，3，4只進行一次比對就使得i向后移動一位（也就是next[j] = 0)
改進演算法如下：
改進之后next[j] = 0,0,0,0,4,成功避免了重復比對
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299870.html
標籤：其他
上一篇：HCNP Routing&Switching之IS-IS鄰居建立、LSDB同步、拓撲計算和路由形成
下一篇：關于API網關（四）——限流