kmp字串模式匹配詳解
kmp字串模式匹配通俗點說就是一種在乙個字串中定位另乙個串的高效演算法。簡單匹配演算法的時間複雜度為o(m*n);kmp匹配演算法。可以證明它的時間複雜度為o(m+n).。
一.簡單匹配演算法
先來看乙個簡單匹配演算法的函式：
int index_bf ( char s [ ], char t [ ], int pos )
if ( t[j] == '\0')
return i; // 匹配成功返回下標
else
return -1; // 串s中(第pos個字元起)不存在和串t相同的子串
} // index_bf
此演算法的思想是直截了當的：將主串s中某個位置i起始的子串和模式串t相比較。即從 j=0 起比較 s[i+j] 與 t[j]，若相等，則在主串 s 中存在以 i 為起始位置匹配成功的可能性，繼續往後比較( j逐步增1 )，直至與t串中最後乙個字元相等為止，否則改從s串的下乙個字元起重新開始進行下一輪的"匹配"，即將串t向後滑動一位，即 i 增1，而 j 退回至0，重新開始新一輪的匹配。
例如：在串s=」abcabcabdabba」中查詢t=」 abcabd」（我們可以假設從下標0開始）:先是比較s[0]和t[0]是否相等，然後比較s[1] 和t[1]是否相等…我們發現一直比較到s[5] 和t[5]才不等。
如圖：當這樣乙個失配發生時，t下標必須回溯到開始，s下標回溯的長度與t相同，然後s下標增1,然後再次比較。如圖：
這次立刻發生了失配，t下標又回溯到開始，s下標增1,然後再次比較。如圖：
這次立刻發生了失配，t下標又回溯到開始，s下標增1,然後再次比較。如圖：
又一次發生了失配，所以t下標又回溯到開始，s下標增1,然後再次比較。這次t中的所有字元都和s中相應的字元匹配了。函式返回t在s中的起始下標3。如圖：
二. kmp匹配演算法
還是相同的例子，在s=」abcabcabdabba」中查詢t=」abcabd」，如果使用kmp匹配演算法，當第一次搜尋到s[5] 和t[5]不等後，s下標不是回溯到1，t下標也不是回溯到開始，而是根據t中t[5]==』d』的模式函式值（next[5]=2，為什麼？後面講），直接比較s[5] 和t[2]是否相等，因為相等，s和t的下標同時增加;因為又相等，s和t的下標又同時增加。。。最終在s中找到了t。
如圖：kmp匹配演算法和簡單匹配演算法效率比較，乙個極端的例子是：
在s=「aaaaaa…aab「(100個a)中查詢t=」aaaaaaaaab」, 簡單匹配演算法每次都是比較到t的結尾，發現字元不同，然後t的下標回溯到開始，s的下標也要回溯相同長度後增1，繼續比較。如果使用kmp匹配演算法，就不必回溯.
對於一般文稿中串的匹配，簡單匹配演算法的時間複雜度可降為o (m+n)，因此在多數的實際應用場合下被應用。
kmp演算法的核心思想是利用已經得到的部分匹配資訊來進行後面的匹配過程。看前面的例子。為什麼t[5]==』d』的模式函式值等於2（next[5]=2），其實這個2表示t[5]==』d』的前面有2個字元和開始的兩個字元相同，且t[5]==』d』不等於開始的兩個字元之後的第三個字元（t[2]=』c』）.
如圖：也就是說，如果開始的兩個字元之後的第三個字元也為』d』,那麼，儘管t[5]==』d』的前面有2個字元和開始的兩個字元相同，t[5]==』d』的模式函式值也不為2，而是為0。
前面我說：在s=」abcabcabdabba」中查詢t=」abcabd」，如果使用kmp匹配演算法，當第一次搜尋到s[5] 和t[5]不等後，s下標不是回溯到1，t下標也不是回溯到開始，而是根據t中t[5]==』d』的模式函式值，直接比較s[5] 和t[2]是否相等。。。為什麼可以這樣？
剛才我又說：「（next[5]=2），其實這個2表示t[5]==』d』的前面有2個字元和開始的兩個字元相同」。請看圖：
因為，s[4] ==t[4]，s[3] ==t[3]，根據next[5]=2，有t[3]==t[0]，t[4] ==t[1]，所以s[3]==t[0]，s[4] ==t[1]（兩對相當於間接比較過了），因此，接下來比較s[5] 和t[2]是否相等。。。
有人可能會問：s[3]和t[0]，s[4] 和t[1]是根據next[5]=2間接比較相等，那s[1]和t[0]，s[2] 和t[0]之間又是怎麼跳過，可以不比較呢？因為s[0]=t[0]，s[1]=t[1]，s[2]=t[2]，而t[0]!
=t[1], t[1]!=t[2],==>s[0]!= s[1],s[1] !
= s[2],所以s[1]!= t[0],s[2] != t[0].
還是從理論上間接比較了。
有人疑問又來了，你分析的是不是特殊輕況啊。
假設s不變，在s中搜尋t=「abaabd」呢？答：這種情況，當比較到s[2]和t[2]時，發現不等，就去看next[2]的值，next[2]=-1，意思是s[2]已經和t[0] 間接比較過了，不相等，接下來去比較s[3]和t[0]吧。
假設s不變，在s中搜尋t=「abbabd」呢？答：這種情況當比較到s[2]和t[2]時，發現不等，就去看next[2]的值，next[2]=0，意思是s[2]已經和t[2]比較過了，不相等，接下來去比較s[2]和t[0]吧。
假設s=」abaabcabdabba」在s中搜尋t=「abaabd」呢？答：這種情況當比較到s[5]和t[5]時，發現不等，就去看next[5]的值，next[5]=2，意思是前面的比較過了，其中，s[5]的前面有兩個字元和t的開始兩個相等，接下來去比較s[5]和t[2]吧。
總之，有了串的next值，一切搞定。那麼，怎麼求串的模式函式值next[n]呢？（本文中next值、模式函式值、模式值是乙個意思。）
三. 怎麼求串的模式值next[n]
定義：（1）next[0]= -1意義：任何串的第乙個字元的模式值規定為-1。
（2）next[j]= -1 意義：模式串t中下標為j的字元，如果與首字元
相同，且j的前面的1—k個字元與開頭的1—k
個字元不等（或者相等但t[k]==t[j]）（1≤k）。
如：t=」abcabcad」 則 next[6]=-1，因t[3]=t[6]
（3）next[j]=k 意義：模式串t中下標為j的字元，如果j的前面k個
字元與開頭的k個字元相等，且t[j] != t[k] （1≤k）。
即t[0]t[1]t[2]。。。t[k-1]==
t[j-k]t[j-k+1]t[j-k+2]…t[j-1]
且t[j] != t[k].（1≤k）;
(4) next[j]=0 意義：除（1）（2）（3）的其他情況。
舉例：01）求t=「abcac」的模式函式的值。
next[0]= -1根據（1）
next[1]=0 根據 (4) 因（3）有1<=k不能說，j=1,t[j-1]==t[0]
next[2]=0 根據 (4) 因（3）有1<=k（t[0]=a）!=（t[1]=b）
next[3]= -1根據 (2)
next[4]=1 根據 (3)t[0]=t[3] 且 t[1]=t[4]即
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...
資料結構與演算法信
美國uiuc大學博士生梅俏竹 資料結構是美國所有一流計算機系的本科核心課程之一，上承計算引論與初級程式設計，下啟高階演算法和計算理論，向來是計算機本科教學的重中之重。我在北大上過的諸多本科基礎課中，無論從課程內容和老師教學下的功夫來看，張銘老師的 資料結構與演算法 課程都是首屈一指的。可以說，將北大...