原文連結
本文是介紹 什麼是 BF算法、KMP算法、BM算法 三部曲之一。
KMP算法 内部涉及到的數學原理與知識太多，本文隻會對 KMP算法 的運作過程、 部分比對表 、next數組 進行介紹，如果了解了這三點再去閱讀其它有關 KMP算法 的文章肯定能有個清晰的認識。
以下的文字描述請結合視訊動畫來閱讀~
定義
Knuth-Morris-Pratt 字元串查找算法，簡稱為 KMP算法，常用于在一個文本串 S 内查找一個模式串 P 的出現位置。
這個算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年聯合發表，故取這 3 人的姓氏命名此算法。
是不是感覺 Donald Knuth 這個名字很眼熟？沒錯，在前面 這或許是講解 Knuth 洗牌算法最好的文章 一文中也出現了他！
KMP算法 的操作流程如下：
- 假設現在文本串 S 比對到 i 位置，模式串 P 比對到 j 位置
-
如果 j = -1，或者目前字元比對成功（即 S[i] == P[j] ），都令 i++，j++，繼續比對下一個字元；
如果 j != -1，且目前字元比對失敗（即 S[i] != P[j] ），則令 i 不變，j = next[j]。此舉意味着失配時，模式串 P相對于文本串 S 向右移動了 j - next [j] 位
- 換言之，将模式串 P 失配位置的 next 數組的值對應的模式串 P 的索引位置移動到失配處
運作過程
以下圖文本串 S 與模式串 P 為例：
首先，列出模式串 P 的所有子串：
| a | |||||||
|---|---|---|---|---|---|---|---|
| b | |||||||
| c | |||||||
然後，求得每一個子串的所有字首與字尾。
字首 指除了最後一個字元以外，一個字元串的全部頭部組合；字尾 指除了第一個字元以外，一個字元串的全部尾部組合。
以第五列為例進行示範。
字首為
字尾為
是以，它的字首字尾的公共元素的最大長度為 2。
求得原模式串 P 的子串對應的各個字首字尾的公共元素的 最大長度表 下圖。
根據最大長度表 去求 next 數組：next 數組相當于“最大長度值” 整體向右移動一位，然後初始值賦為-1。
好了，擷取了 next 數組 後，KMP 算法 的操作就很清晰了。
将模式串 P 與文本串 S 的字母一個個進行比對，當失配的時候，模式串向右移動。
怎麼移動？
比如模式串的 b 與文本串的 c 失配了，找出失配處模式串的 next數組 裡面對應的值，這裡為 0，然後将索引為 0 的位置移動到失配處。
後記
市面上好多講解 KMP算法 的文章的寫的太混亂了，很多人是以産生了恐懼，這一章目的就是為了能讓大家能大概了解 KMP算法 的運作過程，不會畏懼 KMP算法 。
來源 | 五分鐘學算法
作者 | 程式員小吳