天天看點

通俗易懂的KMP算法詳解

角色:

甲:abbaabbaaba

乙:abbaaba

乙對甲說:「幫忙找一下我在你的哪個位置。」

甲從頭開始與乙一一比較,發現第 7 個字元不比對。

要是在往常,甲會回退到自己的第 2 個字元,乙則回退到自己的開頭,然後兩人開始重新比較。​​[1]​​這樣的事情在字元串王國中每天都在上演:不比對,回退,不比對,回退,……

但總有一些妖豔字元串要花出自己不少的時間。

上了年紀的甲想做出一些改變。于是甲把乙叫走了:「你先一邊玩去,我自己研究下。」

甲給自己定了個小目标:發生不比對,自己不回退。

甲發現,若要成功與乙比對,必須要比對 7 個字元。也就是說,就算自己回退了,在後續的比對流程中,肯定還要比對自己的第 7 個字元。

當在甲的某個字元 c 上發生不比對時,甲即使回退,最終還是會重新比對到字元 c 上。

那幹脆不回退,豈不美哉!

甲不回退,乙必須回退地盡可能少,并且乙回退位置的前面那段已經和甲比對,這樣甲才能不用回退。

如何找到乙回退的位置?

「不比對發生時,前面比對的那一小段 abbaab 于我倆是相同的」,甲想,「這樣的話,用 abbaab 的頭部去比對 abbaab 的尾部,最長的那段就是答案。」

具體來說,
abbaab 的頭部有 a, ab, abb, abba, abbaa(不包含最後一個字元。下文稱之為「字首」)
abbaab 的尾部有 b, ab, aab, baab, bbaab(不包含第一個字元。下文稱之為「字尾」)
這樣最長比對是 ab,乙回退到第三個字元和甲繼續比對。      

「要計算的内容隻和乙有關」,甲想,「那就假設乙在所有位置上都發生了不比對,乙在和我比對之前把所有位置的最長比對都算出來(算個長度就行),生成一張表,之後我倆發生不比對時直接查這張表就行。」

據此,甲總結出了一條甲方規則:

所有要與甲比對的字元串,必須先自身比對:對每個子字元串 [0...i],算出其「相比對的字首與字尾中,最長的字元串的長度」。

甲把乙叫了回來,告訴他新出爐的甲方規則。

「小 case,我對自己還不了解嗎」,乙眨了一下眼睛,「那我回退到第三個字元和你繼續比對就行了」。

有些算法,适合從它産生的動機,如何設計與解決問題這樣正向地去介紹。但KMP算法真的不适合這樣去學。最好的辦法是先搞清楚它所用的資料結構是什麼,再搞清楚怎麼用,最後為什麼的問題就會有恍然大悟的感覺。我試着從這個思路再介紹一下。大家隻需要記住一點,PMT是什麼東西。然後自己臨時推這個算法也是能推出來的,完全不需要死記硬背。KMP算法的核心,是一個被稱為部分比對表(Partial Match Table)的數組。我覺得了解KMP的最大障礙就是很多人在看了很多關于KMP的文章之後,仍然搞不懂PMT中的值代表了什麼意思。這裡我們抛開所有的枝枝蔓蔓,先來解釋一下這個資料到底是什麼。對于字元串“abababca”,它的PMT如下表所示:

通俗易懂的KMP算法詳解

就像例子中所示的,如果待比對的模式字元串有8個字元,那麼PMT就會有8個值。

我先解釋一下字元串的字首和字尾。如果字元串A和B,存在A=BS,其中S是任意的非空字元串,那就稱B為A的字首。例如,”Harry”的字首包括{”H”, ”Ha”, ”Har”, ”Harr”},我們把所有字首組成的集合,稱為字元串的字首集合。同樣可以定義字尾A=SB, 其中S是任意的非空字元串,那就稱B為A的字尾,例如,”Potter”的字尾包括{”otter”, ”tter”, ”ter”, ”er”, ”r”},然後把所有字尾組成的集合,稱為字元串的字尾集合。要注意的是,字元串本身并不是自己的字尾。

有了這個定義,就可以說明PMT中的值的意義了。PMT中的值是字元串的字首集合與字尾集合的交集中最長元素的長度。例如,對于”aba”,它的字首集合為{”a”, ”ab”},字尾 集合為{”ba”, ”a”}。兩個集合的交集為{”a”},那麼長度最長的元素就是字元串”a”了,長 度為1,是以對于”aba”而言,它在PMT表中對應的值就是1。再比如,對于字元串”ababa”,它的字首集合為{”a”, ”ab”, ”aba”, ”abab”},它的字尾集合為{”baba”, ”aba”, ”ba”, ”a”}, 兩個集合的交集為{”a”, ”aba”},其中最長的元素為”aba”,長度為3。

好了,解釋清楚這個表是什麼之後,我們再來看如何使用這個表來加速字元串的查找,以及這樣用的道理是什麼。如圖 1.12 所示,要在主字元串"ababababca"中查找模式字元串"abababca"。如果在 j 處字元不比對,那麼由于前邊所說的模式字元串 PMT 的性質,主字元串中 i 指針之前的 PMT[j −1] 位就一定與模式字元串的第 0 位至第 PMT[j−1] 位是相同的。這是因為主字元串在 i 位失配,也就意味着主字元串從 i−j 到 i 這一段是與模式字元串的 0 到 j 這一段是完全相同的。而我們上面也解釋了,模式字元串從 0 到 j−1 ,在這個例子中就是”ababab”,其字首集合與字尾集合的交集的最長元素為”abab”, 長度為4。是以就可以斷言,主字元串中i指針之前的 4 位一定與模式字元串的第0位至第 4 位是相同的,即長度為 4 的字尾與字首相同。這樣一來,我們就可以将這些字元段的比較省略掉。具體的做法是,保持i指針不動,然後将j指針指向模式字元串的PMT[j −1]位即可。

簡言之,以圖中的例子來說,在 i 處失配,那麼主字元串和模式字元串的前邊6位就是相同的。又因為模式字元串的前6位,它的前4位字首和後4位字尾是相同的,是以我們推知主字元串i之前的4位和模式字元串開頭的4位是相同的。就是圖中的灰色部分。那這部分就不用再比較了。

通俗易懂的KMP算法詳解

有了上面的思路,我們就可以使用PMT加速字元串的查找了。我們看到如果是在 j 位 失配,那麼影響 j 指針回溯的位置的其實是第 j −1 位的 PMT 值,是以為了程式設計的友善, 我們不直接使用PMT數組,而是将PMT數組向後偏移一位。我們把新得到的這個數組稱為next數組。下面給出根據next數組進行字元串比對加速的字元串比對程式。其中要注意的一個技巧是,在把PMT進行向右偏移時,第0位的值,我們将其設成了-1,這隻是為了程式設計的友善,并沒有其他的意義。在本節的例子中,next數組如下表所示。

通俗易懂的KMP算法詳解
1 // 傳回值為首次比對的串的第一個字元的下标
 2 /* 
 3     不能寫 while( i < t.length() && j < p.length() ),
 4     因為當j = -1時,因為p.length()是無符号整數,則-1 > p.length(),
 5     這樣就産生了錯誤
 6     是以要事先用有符号整數儲存 t.length()和p.length()的值
 7 */
 8 int kmp(string t, string p)
 9 {
10     int i = 0, j = 0;
11 
12     int tlen = t.length();
13     int plen = p.length();
14     while (i < tlen && j < plen)
15     {
16         if (j == -1 || t[i] == p[j])
17         {
18             ++i;
19             ++j;
20         }
21         else
22         {
23             j = nxt[j];
24         }
25     }
26 
27     if (j == plen)
28         return i - j;
29     else
30         return -1;
31 }      

好了,講到這裡,其實KMP算法的主體就已經講解完了。你會發現,其實KMP算法的動機是很簡單的,解決的方案也很簡單。遠沒有很多教材和算法書裡所講的那麼亂七八糟,隻要搞明白了PMT的意義,其實整個算法都迎刃而解

現在,我們再看一下如何程式設計快速求得next數組。其實,求next數組的過程完全可以看成字元串比對的過程,即以模式字元串為主字元串,以模式字元串的字首為目标字元串,一旦字元串比對成功,那麼目前的next值就是比對成功的字元串的長度

具體來說,就是從模式字元串的第一位(注意,不包括第0位)開始對自身進行比對運算。 在任一位置,能比對的最長長度就是目前位置的next值。如下圖所示。

通俗易懂的KMP算法詳解
通俗易懂的KMP算法詳解
通俗易懂的KMP算法詳解
通俗易懂的KMP算法詳解
通俗易懂的KMP算法詳解

求next數組值的程式如下所示:

1 int nxt[1010];
 2 
 3 // 已經有庫函數叫做next,是以next數組的命名不能再叫做next,否則會報next不明确的錯誤,這裡改為nxt
 4 void getNext(string p, int nxt[])
 5 {
 6     nxt[0] = -1;
 7     int i = 0, j = -1;
 8     
 9     int plen = p.length();
10     while (i < plen)
11     {
12         if (j == -1 || p[i] == p[j])
13         {
14             ++i;
15             ++j;
16             nxt[i] = j;    // nxt[1]恒等于0 
17         }
18         else
19         {
20             j = nxt[j];
21         }
22     }
23 }      

複雜度估計:

假設原串長度為n, 比對串長度為m。我們可以看到,比對串每次往前移動,都是一大段一大段移動,假設比對串裡不存在重複的字首和字尾,即next的值都是-1,那麼每次移動其實就是一整個比對串往前移動m個距離。然後重新一一比較,這樣就比較m次,概括為,移動m距離,比較m次,移到末尾,就是比較n次,O(n)複雜度。 假設比對串裡存在重複的字首和字尾,我們移動的距離相對小了點,但是比較的次數也小了,整體代價也是O(n)。是以複雜度是一個線性的複雜度O(n)。同理,求next數組的複雜度為O(m),總體就為O(m+n)。