kmp演算法的功能是要在主串s中尋找是否存在子串t。理解這個演算法的核心是next函式。
next函式見下面。由於case1和case3情況比較簡單，我們僅對case2進行**。
case2中做的事情是在子串t中（t[1]~t[j]）的範圍內找到最大重疊的字首和字尾。並且要求字首頂頭，字尾頂尾。即字首從t[1]（即p1）開始，字尾到t[j-1](即p（j-1）)為止。
next函式實現如下。
程式1如上所示，j為字尾的指標，k為字首的指標。當t[j]==t[k]時，繼續比較t[j+1]和t[k+1]，並且將k賦值給next[j]，此時串t[1]~t[j-1]中，最大匹配前字尾的長度為(k-1)；若t[j]!=t[k]，此時k回溯為next[k]。
我們接下來講解為什麼k回溯為next[k]，而不是其他值
如圖1所示，在子串t中求前字尾最大匹配數量。當t[j]!=t[k]時，即t[j]和t[k]不匹配，但同時也說明之前還是匹配的，如圖1兩個藍色塊a:
t[1]~t[k-1]與b:t[j-k+1]~t[j-1]是匹配的。此時可以將t[1]到t[j]看做串s』，將串t[1]到t[k]看做t』，那麼問題轉變成主串s』和子串t』的匹配問題，正好對應的是kmp問題。
如圖2所示。串s』代表主串，串t』代表子串，主串和子串比較到第k位的時候發生不匹配，此時在不減少主串指標j的情況下，尋找子串中新的指標位置k』，使得下一次迭代時，直接比較s』[j]和t』[k』]就可以了（如圖3所示）。
圖1圖2
圖3如圖3所示，子串t』在位置k發生與s』不匹配時，k回溯到k』位置。由kmp演算法思想可知，k』=next[k]。這就又巧妙借用了kmp演算法的思想，從比較巨集觀的角度解釋了為什麼不匹配時，k回溯為next[k]。
如果你覺得上面的解釋還不夠形象和具體，下面我們再以微觀的例項進一步闡釋這一問題：為什麼是回溯位置k』是next[k]，而不是其他的值。
當k』=next[k]時，根據next函式的含義，此時代表在串t』[1]到t』[k-1]之間，找到最大重疊的前字尾長度為(k』-1)，圖4分別用綠色塊d和e表示最大匹配的字首和字尾。由於藍色塊a和塊b是匹配的，因此在塊b中也存在對應的綠色塊f和g，四個綠色塊互相都是匹配的，由於這裡推斷出d和g匹配，因此程式無需再比較（節省計算步驟），那麼就可以直接比較s』[j]和t』[k』]了。此時t』[1]對齊s』中的元素s』[j-k』+1]。
圖4通過上一段的說明，我們知道將k回溯為next[k]是完全可以的，那麼k回溯為其他值是否可以呢？接下來我們用反證的方法，先假設可以，推導出矛盾，再推翻。當k回溯為next[k]時，移動子串t』的結果是t』[1]對應s』[j-k』+1]（如圖4所示）。
反證時我們分別考慮t』[1]對應s』中其他值的幾種情況：(1) t』[1]移動後對應s』區間位於{s』[1]~s』[j-k+1]，如圖5區間（a）所示； (2) t』[1]移動後對應s』區間是{s』[j-k+1]~s』[j-k』+1]，如圖5區間（b）所示;；(3) t』[1]移動後對應s』區間是{s』[j-k』+1]~s』[j]，如圖5區間（c）所示。下面分別討論以上三種情況是否成立。
圖5（1） 若t』移動後t』[1]的位置對應在s』區間(a)的位置m，如圖6所示。
若此種情況可以匹配，則在s』中必然存在乙個綠色塊q (s』[m]~s』[j-1])與t』中h（t』[1]~t』[k』-1]）匹配。由於s』和t』其實是同乙個串，因此s』[1]~s』[k-1]與q (s』[m]~s』[j-1])相匹配，推斷出s』[1]~s』[j-1]串中，存在最長匹配前字尾長度為（k』-1）（或j-m）。而由之前所知，k=next[j]，可知s』[1]~s』[j-1]中前字尾最大匹配長度為(k-1)。
由於(k』-1)>(k-1)，超越了已知的前字尾匹配的最大長度(即綠色部分大於藍色部分)，因此假設不成立，t』[1]位置不能位於區間(a)。
圖6（2） 若t』移動後t』[1]的位置對應s』的位置m位於區間(b)，如圖7所示。
此時s』和』對應的匹配部分記為綠色塊q與h，由於s』中前字尾兩個藍色塊是匹配的，可以推斷出，在藍色塊（s』[1]~s』[k-1]）中，存在前字尾匹配的最大長度就是綠色塊h，其長度為(j-m)，大於先前已經知道的藍色塊中前字尾匹配的最大長度（即圖5中的綠色部分，長度為圖5中所示的k』-1）。也推出矛盾。假設不成立，t』[1]位置不能位於區間(b)。
圖7（3） 若t』移動後t』[1]的位置對應在s』中位置m位於區間(c)中，如圖8所示。
我們在此說明當前比較時，t』[1]的位置不能越過區間(b)(c)的交界而進入區間(c)，因為這樣會遺漏掉匹配的情況。因為t』[1]是逐漸向右移動的，按照樸素的字串匹配演算法，每次僅能移動乙個元素。我們為了提高計算效率，才根據kmp演算法一次移動多個元素，但移動不能過量。
根據圖5，我們知道t』[1]移動到與s[j-k』+1]對齊時，存在匹配。而移動到區間(c)就是移動過量了，會遺漏掉匹配的情況。後續比較可能會移動到區間(c)，但是當前不會。
因此情況（3）也不成立。
圖8綜合以上三種情況，t』[1]只能移動到圖5所示的位置，即k回溯為next[k]。
KMP演算法 如何理解
假設，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...
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 ...
演算法與程式框圖知識講解
學習目標 1.初步建立演算法的概念 2.讓學生通過豐富的例項體會演算法的思想 3.讓學生通過對具體問題的 初步了解演算法的含義 4.掌握程式框圖的概念 5.會用通用的圖形符號表示演算法，掌握演算法的三個基本邏輯結構 6.掌握畫程式框圖的基本規則，能正確畫出程式框圖.要點梳理 要點一 演算法的概念 1...