怎麼理解kmp演算法中的next數組?

01-04

最近在看字元串匹配的相關演算法。然後這邊有點難理解。求指點。

阮一峰的字元串匹配的KMP演算法中詳細解釋了前綴、後綴的概念，但是沒有提到next數組的求法。雖然July的從頭到尾徹底理解KMP（2014年8月22日版）中詳細解釋了next數組的求法，但是關於k = next[k]這一塊講的還不是太好。下面，我啰嗦幾句，咳咳。(ps：往下閱讀前建議先看July的那篇文章)

模式字元串記為P(下標從0開始)，next[q] = k 表示P[q]之前的子串中，存在長度為k的相同前綴和後綴，即P[0]~P[k-1]與P[q-k]~P[q-1]依次相同。如果P[k] = P[q]，那麼next[q+1] = k+1，此時表示P[q+1]之前的子串中，存在長度為k+1的相同前後綴，這應該不成問題。下面貼張圖詳細表示：

如果P[k] != P[q]，那麼說明next[q+1] 不會是 k+1，也就是說P[q+1]之前的子串中，不會存在長度為k+1的相同前後綴。那麼我們就要去尋找長度更短的相同前後綴，假設長度為j，此時P[0]~P[j-1]和P[q-j]~P[q-1]依次相同。下面再貼張圖：

接著我們比較P[q]和P[j]是否相同，如果相同，則next[q+1] = j+1；如果不同，則按照k = next[k]遞歸查找。說到這，大家應該可以看出這裡的j = next[k]。如果還不明白，看看next數組的定義，next[k] = j 表示P[k]之前的子串中，存在長度為j的相同前後綴。從圖2可以看出，P[0]~P[j-1]和P[k-j]~P[k-1]是依次相同的。啰嗦完了。PS：圖片來自下面的文章

【經典演算法】——KMP，深入講解next數組的求解

請看阮一峰的日誌字元串匹配的KMP演算法

最好理解的辦法是構造一個DFA來描述pattern，出現pattern不匹配的時候，你實際上可以根據這個DFA推測出之前出現的字元有哪些可以被重複利用。

去看sedgewick的algorithms。他老人家講解很多演算法都別具一格，比如他的紅黑樹。直達問題本質，寫出來的代碼也非常精鍊。推薦一下。

阮一峰日誌中的解釋法與演算法導論中的相同，下面是從演算法導論中截圖

可是，我查看了 KMP 的原始論文就是（K，M，P 三個傢伙寫的原文），截圖如下

誰能告訴我劃圈的地方為什麼會不同，另外我查看了《大話數據機構》與嚴蔚敏《數據結構》，這兩本里的表示方法符合KMP的原文。為什麼這兩種表示會有不同呢？

相當於先把自己匹配了一遍，建了個自動機

知乎這個費勁的編輯功能呀

證明和代碼

理解KMP - xujiazhe blog

那個next屬於其實就是一個有限狀態自動機。

請參閱演算法導論第32章

阮一峰和July的書（博客），都在從不同角度講了kmp演算法。阮的博客講了kmp的大概實現原理，通俗易懂。July則從各個方面講kmp，講的比較詳細。但是對於next數組的求發，July也有講，但是只是說失配時，遞歸前綴索引。並沒有詳細展開講為什麼這樣就可以求得next數組。

對於next數組的演算法，另外找了一篇文章，感覺講的比較通透，看完豁然開朗。

KMP演算法的Next數組詳解 - 唐小喵 - 博客園

自己的一點點小理解：字元串匹配的KMP演算法

可以去搜下 matrix67 的blog 介紹得不錯