假設，p向右移動一定距離後，第k個字元p[k]和s[i]進行比較。
此時如上圖，當p[j]和s[i]失配後，i不動，將p前移到k，讓p[k]和s[i]繼續匹配。現在的關鍵是k的值是多少？
通過上圖，我們發現，因為黃色部分表示已經匹配了的結果（因為是到了s[i]和p[j]的時候才失配，所以si-j+1si-j+2…si-1 = p1p2…pj-1，見黃色的部分）。所以有：
1、si-k+1si-k+2…si-1 = pj-k+1pj-k+2…pj-1。
所以當p前移到k時，有：
2、si-k+1si-k+2…si-1 = p1p2…pk-1。
通過1，2有
pj-k+1pj-k+2…pj-1 = p1p2…pk-1。
呵呵，此時我們的任務就是求這個k值了。。。
參考：2. 求出 k 值
按照課本的求法就可以處理。
課本是已知前j個元素的「字首函式值」，如何求的j+1個元素的字首函式值。這裡有乙個思路要發生轉變的地方，把乙個模式串分成兩個部分，因為我們要找k使得 pj-k+1pj-k+2…pj-1 = p1p2…pk-1 ，而這本身就是乙個模式匹配問題，所以把模式串的前邊部分的子串當作「新的模式串」，這樣就很容易理解為什麼當 tk!=tj時，t1…tnext[k]-1 = tj-（next[k]-1）…tj-1 了。
因為這時候 tk匹配失敗，需要進一步移動模式子串，所以移動的位置就是 next[k]。
KMP演算法步驟分析
注 先計算好next值進而推出nextval數值，可在csnd上找到求解方法。對於上述kmp演算法第趟匹配,有一定的難度！接下來，我來分析一下。先給主串和模式串進行編號 主串 a b c a a b b a b c a b a a c b a c b a 編號i 1 2 3 4 5 6 7 8 9 ...
KMP演算法中next講解
kmp演算法的功能是要在主串s中尋找是否存在子串t。理解這個演算法的核心是next函式。next函式見下面。由於case1和case3情況比較簡單，我們僅對case2進行 case2中做的事情是在子串t中 t 1 t j 的範圍內找到最大重疊的字首和字尾。並且要求字首頂頭，字尾頂尾。即字首從t 1 ...
如何理解培訓
關於調整龍山頭煤礦安全監測監控及維護管理組織機構的決定 為了認真落實 安全第一，預防為主，綜合治理 的煤礦安全生產方針，確保煤礦安全生產，經礦研究決定成立龍山頭煤礦安全監測監控及維護管理小組。一 組織機構組成 管理小組組長 劉德明 副組長 牛雙鑫 成員 王畢金袁輝何維鑫龍光明溫碧娟黃娟楊紅連 二 管...