(回憶大學所學)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賦值,稱為改進版。
推薦閱讀:
※在GitHub上搭建自己的個人主頁
※Spring Cloud雲架構 - commonservice-sso服務搭建
※HTTP協議幾個版本的比較
※心血來潮,試試專欄。
※余艾冰:計算是理解顆粒體系的強有力工具 | NSR專欄