個人覺得這篇文章是網上的介紹有關kmp演算法更讓人容易理解的文章了，確實說得很「詳細」，耐心地把它看完肯定會有所收穫的～～，另外有關模式函式值next[i]確實有很多版本啊，在另外一些物件導向的演算法描述書中也有失效函式 f(j)的說法，其實是乙個意思，即next[j]=f(j-1)+1，不過還是next[j]這種表示法好理解啊：
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 next[2]=0 根據 (4) 因（3）有1<=k next[3]= -1根據 (2)
next[4]=1 根據 (3)t[0]=t[3] 且 t[1]=t[4]
即 若t=「abcab」將是這樣：
為什麼t[0]==t[3],還會有next[4]=0呢, 因為t[1]==t[4], 根據 (3)」 且t[j] != t[k]」被劃入（4）。
02）來個複雜點的，求t=」ababcaabc」 的模式函式的值。
next[0]= -1 根據（1）
next[1]=0 根據(4)
next[2]=-1 根據 (2)
next[3]=0 根據 (3) 雖t[0]=t[2] 但t[1]=t[3] 被劃入（4）
next[4]=2 根據 (3) t[0]t[1]=t[2]t[3] 且t[2] !=t[4]
next[5]=-1根據 (2)
next[6]=1 根據 (3) t[0]=t[5] 且t[1]!=t[6]
next[7]=0 根據 (3) 雖t[0]=t[6] 但t[1]=t[7] 被劃入（4）
next[8]=2 根據 (3) t[0]t[1]=t[6]t[7] 且t[2] !=t[8]
即只要理解了next[3]=0，而不是=1，next[6]=1，而不是= -1，next[8]=2，而不是= 0，其他的好象都容易理解。
03) 來個特殊的，求 t=」abcabcad」 的模式函式的值。
next[5]= 0根據 (3) 雖t[0]t[1]=t[3]t[4],但t[2]==t[5]
next[6]= -1根據 (2) 雖前面有abc=abc,但t[3]==t[6]
next[7]=4 根據 (3) 前面有abca=abca,且 t[4]!=t[7]
KMP字串模式匹配詳解
kmp字串模式匹配通俗點說就是一種在乙個字串中定位另乙個串的高效演算法。簡單匹配演算法的時間複雜度為o m n kmp匹配演算法。可以證明它的時間複雜度為o m n 一.簡單匹配演算法 先來看乙個簡單匹配演算法的函式 int index bf char s char t int pos if t j...
C語言 字串函式大全和詳解
atof 將字串轉換成浮點型數 atoi 將字串轉換成整型數 atol 將字串轉換成長整型數 strtod 將字串轉換成浮點數 strtol 將字串轉換成長整型數 strtoul 將字串轉換成無符號長整型數 toascii 將整型數轉換成合法的ascii 碼字元 toupper 將小寫字母轉換成大寫...
C語言 字串函式大全和詳解
void memset void dest,int c,size t count 將dest前面count個字元置為字元c.返回dest的值.void memmove void dest,const void src,size t count 從src複製count位元組的字元到dest.如果src...