通俗了解KMP算法

通俗了解KMP算法

如果要比較字元串是否相等或包含，通常的情況下一般是一個個疊代的去比較，比如要比較的字元串長度為20，那麼就要比較20次，這樣的效率是非常低的。

上面的字元串比較效率太低，我們是否能夠獲得已知的情況，來減少對字元串判斷的次數呢？比如說子字元串(要比較的字元串)和父字元串(被比較的字元串)來比較是否相等，首先子字元串比對了前面的3個字元都相等，那我們是否可以跳過3個長度呢？因為3個字元都已經比對過了，是以不用在比對了，這樣對一個個疊代好得多。說的不清楚，那就看圖文吧！

步驟一：

首先 f 和 a比較，發現不等于，然後前進一位

步驟二：

f 又和 b比較，發現不等于，然後又前進一位，直到比對父字元串的f

步驟三：

子字元串的f和父字元串的f，比對相等，然後比對第二個字元串a，然後發現a和b不等，然後繼續疊代。(請不要在意父字元的長度到了尾部，懂是這個意思就可以了。)

步驟四：

子字元串的f和父字元串的b并不相等，而父字元串後面沒有字元了，是以可隻父字元串并沒有包含字元串。

為了得出這個結論，我們把父字元串的所有字元都比較了一次，如果有長度為100的父字元串，難道我們要比較100次嗎？那如果有1M大小的字元串呢？

假設我們有這麼一張表，先别管這表幹嘛的，也别管表的資料是怎麼來的，後面會說。

首先還是同樣的步驟，子字元串一直對比到父字元串的A處

子：A和父：A 一樣，在比較下一個字元B又是一樣的，然後直到子D和父A，那裡就不一樣了，注意我們不會在一個個比較，我們要通過KMP算法得出要跳四位。

問題：

那你是怎麼用KMP算法得出要跳四位呢？

在步驟一的那個表中，最後一個配置值：B，對應的是2，然後用公式：已比對的字元數-對應的部分比對值=移動位數，那麼就是6-2=4

然後就跳四位：

後面的依次論推，現在重點是看那張表是怎麼算的。

我們是通過子串：A B C D A B D來計算出那神奇的表格。

我們将它們拆分：

A的字首和字尾為空，共有元素長度為0

AB的字首為A，字尾為B，共有元素長度為0

ABC的字首為[A,AB]，字尾為：[BC、C]，共有元素長度為0

ABCD的字首為[A,AB,ABC]，字尾為[BCD、CD、D]，共有元素長度為0

ABCDA的字首為[A、AB、ABCD]，字尾為[BCDA、CDA、DA、A]，有一個共有元素A，是以長度為1

後面的自己就可以推出來了，這就表資料的來由，而這種跳躍的算法也就是KMP算法啦