（回憶大學所學）KMP演算法

來自專欄回憶大學所學（計算機篇）9 人贊了文章

一、什麼是kmp演算法？（基本概念）

什麼是kmp演算法呢？其實就是一個字元串匹配的演算法。

那什麼是字元串匹配呢？其實就是在一個字元串（主串）里查找另一個字元串（子串）。

那什麼是字元串呢？其實就是由零個或有限個字元組成的有限序列。

如："abcdefg"是一個長度為7的字元串。

如："abcdefg"是主串，而"def"就是子串（子串是主串的一部分）。

我們一般把用於查找的字元串叫模式串，被查找的字元串叫文本串。

如：在"abcdefg"查找"def"，那"abcdefg"就是文本串，"def"就是模式串。

kmp演算法，是Kunth、Morris和Pratt三位前輩研究得出的，所以叫kmp演算法，但是江湖人士更願意叫它「看毛片」演算法。（別問我是怎麼知道的）

二、簡單匹配演算法（了解kmp的基礎）

在講kmp之前，我們先來看一下簡單匹配演算法，它是一種比kmp效率低的字元串匹配演算法。

簡單匹配演算法，又稱暴力搜索，也就是無腦窮舉法。

為了方便理解，我們畫圖示意：

三、KMP演算法（重頭戲來了）

在上圖中，我們已經知道了簡單匹配演算法中有部分步驟是可以省略的，而且文本串的地址也是可以不用回溯的，但是在這些基礎之上，我們還需要了解一些其他概念（前綴，後綴，真前綴，真後綴，最長公共真前後綴，NEXT表），才能準確地表達KMP演算法。

（1）基本概念（以"ababc"為例）

前綴："a"、"ab"、"aba"、"abab"、"ababc"都是"ababc"的前綴

真前綴："a"、"ab"、"aba"、"abab"都是"ababc"的真前綴

後綴："c"、"bc"、"abc"、"babc"、"ababc"都是"ababc"的後綴

真後綴："c"、"bc"、"abc"、"babc"都是"ababc"的後綴

最長公共綴："ab"是"abab"的最長公共綴

為了理解再次舉例："abc"是"abcabc"的最長公共綴

單個字元是沒有最長公共綴，如"a"就沒有最長公共綴，所以最長公共綴準確地說應該是最長公共真前後綴

NEXT表：由所有真前綴的最長公共綴組成的數表（如果不是真前綴，而只是前綴的話，是未改進的NEXT表）

註：NEXT表有很多名稱，如前綴表、部分匹配表，國內的教材一般叫它NEXT數組，關於NEXT表的具體求法，下圖會講到

（2）圖解KMP

有的教材，把KMP演算法分為兩種，一種是改進版，一種是未改進版。

如果直接通過NEXT表給P1~Pn賦值的這種是未改進版，在特殊情況下，會有明顯的多餘步驟。（此時的NRET表用的是前綴，而非真前綴）

如果像上圖中所示，設P1=-1，然後通過NEXT表給P2~Pn賦值，稱為改進版。