KMP算法 內部涉及到的數(shù)學原理與知識太多，本文只會對 KMP算法 的運行過程、 部分匹配表 、next數(shù)組 進行介紹，如果理解了這三點再去閱讀其它有關 KMP算法 的文章肯定能有個清晰的認識。

以下的文字描述請結合視頻動畫來閱讀~

定義

Knuth-Morris-Pratt 字符串查找算法，簡稱為 KMP算法，常用于在一個文本串 S 內查找一個模式串 P 的出現(xiàn)位置。

這個算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年聯(lián)合發(fā)表，故取這 3 人的姓氏命名此算法。

是不是感覺 Donald Knuth 這個名字很眼熟？沒錯，在前面 這或許是講解 Knuth 洗牌算法最好的文章 一文中也出現(xiàn)了他！

KMP算法 的操作流程如下：

• 假設現(xiàn)在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置

• 如果 j = -1，或者當前字符匹配成功（即 S[i] == P[j] ），都令 i++，j++，繼續(xù)匹配下一個字符；
  如果 j != -1，且當前字符匹配失?。?S[i] != P[j] ），則令 i 不變，j = next[j]。此舉意味著失配時，模式串 P相對于文本串 S 向右移動了 j - next [j]  位

• 換言之，將模式串 P 失配位置的 next 數(shù)組的值對應的模式串 P 的索引位置移動到失配處

運行過程

以下圖文本串 S 與模式串 P 為例：

首先，列出模式串 P 的所有子串：

然后，求得每一個子串的所有前綴與后綴。

前綴 指除了最后一個字符以外，一個字符串的全部頭部組合；后綴 指除了第一個字符以外，一個字符串的全部尾部組合。

以第五列為例進行演示。

前綴為

后綴為

因此，它的前綴后綴的公共元素的最大長度為 2。

求得原模式串 P 的子串對應的各個前綴后綴的公共元素的 最大長度表 下圖。

根據(jù)最大長度表 去求 next 數(shù)組：next 數(shù)組相當于“最大長度值” 整體向右移動一位，然后初始值賦為-1。

好了，獲取了 next 數(shù)組 后，KMP 算法 的操作就很清晰了。

將模式串 P 與文本串 S 的字母一個個進行匹配，當失配的時候，模式串向右移動。

怎么移動？

比如模式串的 b 與文本串的 c 失配了，找出失配處模式串的 next數(shù)組 里面對應的值，這里為 0，然后將索引為 0 的位置移動到失配處。

后記

市面上好多講解 KMP算法 的文章的寫的太混亂了，很多人因此產生了恐懼，這一章目的就是為了能讓大家能大概理解 KMP算法 的運行過程，不會畏懼 KMP算法 。