快速字符串匹配一: 看毛片算法（KMP）
- 2019 年 10 月 3 日
- 筆記
前言
由於需要做一個快速匹配敏感關鍵詞的服務，為了提供一個高效，準確，低能耗的關鍵詞匹配服務，我進行了漫長的探索。這裡把過程記錄成系列博客，供大家參考。
在一開始，接收到快速敏感詞匹配時，我就想到了 KMP 翻譯過來叫「看毛片「的算法，因為大學的時候就學過它。聽說到它的效率非常高。把原本字符串匹配效率 O(n*m) 縮短到了O(n+m)，把✖️變成了➕，真是了不得。
每次我回顧 KMP 算法時，都會發現自己是個小白，或者每次回顧時，都發現上次因為回顧而寫的總結居然是錯的！所以為了學習快速字符串匹配，並再次溫故 KMP ，所以我決定使用 KMP 算法試一試。如果以後在面試的時候，可以將KMP 完整的寫出來，那豈不是很牛逼？
孔子說過的「溫故而知新」 真的是很有道理的，經過這次回顧，我覺得是時候為此寫一篇全新的博客了，因為這次的理解肯定是正確的！
KMP 快是因為啥呢？是因為利用了字符串公共前後綴的特性，加快了匹配速度，但是轉念一想，敏感關鍵詞公共前後綴相等的情況可是很少的呀。那還有必要用KMP 嗎？
當然有必要了，所謂技多不壓身，了解掌握一種算法准沒壞處，而且還可以比較 KMP 和 C# 中String.Contains()的效率，開拓自己的眼界。
KMP
以前在學習 KMP 的時候，我也看了網上很多博客，關於這個算法講解的博客是非常多的，而且講解的都很細緻。奈何我每看過一次，就會忘記一次。所以這次溫故，我是完全在紙上畫畫，自己理解的。畢竟自己的思路不容易忘，而別人的思路總是很容易忘的。並且，理解一個算法，得找到適合自己的角度。
因此我理解 KMP 算法的角度，就是 字符串前綴和後綴，在我的腦子裡，用前綴和後綴去理解 KMP 是很容易的。
公共前後綴長度
前綴和後綴，很容易理解，就是一個字符串的前半部分和後半部分。比如字符串 a b c x y a b c 的前綴有
a
a b
a b c 等等，後綴有
c
b c
a b c等等。
那麼公共前後綴的意思就是，前綴和後綴相等。在上面這個例子中，公共前後綴 就是 a b c，長度為3。請注意，公共前後綴 和 迴文串是不一樣的哦。
a b c x y c b a 的公共前後綴，只是a ,而不是a b c。
原始的字符串匹配
了解完 公共前後綴後。暫且放在一旁，去了解一下，原始的字符串匹配。
首先我們把 待匹配的字符串叫做 文本字符串，匹配的字符串叫做匹配字符串，比如我們要在 a b c x y a b c x y a 中匹配 a b c x y a b c y 是否存在。
於是 文本字符串 S 就是 ：a b c x y a b c x y a
匹配字符串 P 就是： a b c x y a b c y
從肉眼看出來，匹配一定是失敗的，因為 匹配字符串 最後一個字母 y 不匹配。
那麼原始的字符串匹配過程就是 暴力的一位一位去比。首先，從第一位開始比較：
0 1 2 3 4 5 6 7 8 9 10 ↓ S a b c x y a b c x y a P a b c x y a b c y ↑第一位，相同比較第二位，一直比到第 8 位
0 1 2 3 4 5 6 7 8 9 10 ↓ S a b c x y a b c x y a P a b c x y a b c y ↑發現不相同，匹配失敗，於是把 匹配字符串 向右移動一位。
0 1 2 3 4 5 6 7 8 9 10 ↓ S a b c x y a b c x y a P a b c x y a b c y ↑繼續重複上面的過程，直到 文本字符串全部遍歷完。 這種方法的效率最差的時候是 O( n*m ) ，就是那種每次都是最後一個字符匹配不了的情況。
快速移動
有沒有更快的方法呢？ 肯定是有的。但是不着急，我們還是按照上面的步驟，繼續走下去。
當 匹配字符串 一直向右移動，移動到第 5 位的時候，終於發現首字母是匹配的情況了。，如下
0 1 2 3 4 5 6 7 8 9 10 ↓ S a b c x y a b c x y a P a b c x y a b c y ↑其實我們發現，從 文本字符串 第一位之後的 b c x y 其實都沒必要匹配的，因為它們和 匹配字符串首字母都不一樣，如果可以直接跳過就好了。
那麼有什麼依據可以直接跳過嗎？當然有，之前的 公共前後綴 就發揮作用了。
a b c x y a b c y 中的子串 a b c x y a b c 的公共前後綴是 a b c，
當一開始，我們發現第 8 位不匹配時，
0 1 2 3 4 5 6 7 8 9 10 ↓ S a b c x y a b c x y a P a b c x y a b c y ↑我們可以直接將 匹配字符串向右移到第五位，然後再從第 8 位繼續進行判斷
0 1 2 3 4 5 6 7 8 9 10 | ↓ S a b c x y a b c x y a P a b c x y a b c y | ↑為什麼呢？
因為a b c = a b c啊，在0 – 7 位的字符串中，它有公共前後綴a b c，所以我們可以把匹配字符串直接移到 公共後綴的起始位置，也就是 第 5位。
因為前面都不用去看，是一定不匹配的!，只有在第五位開始匹配，才有可能成功。
移動的結果，起始就是將一個字符串的前綴部分，移到和後綴部分對齊。這是成功匹配的前提。你可以想像成 ：匹配字符串的子串一直在找自己的後綴，然後靠上去，去匹配。
如下
後綴 a b c x y a b c a b c x y a b c 前綴那麼這樣移動之後，咱們就可以接着 第 8 位 繼續往下匹配，而不用從頭再來了。所以這種方法下，文本字符串只遍歷一次，它不會倒退的。
這就是我所理解的 KMP 算法的核心思想。** KMP 就是利用字符串的前綴和後綴做文章**
具體過程
KMP 算法的物理核心思想理解了，接下來就是代碼實現了。如果保存 匹配字符串的公共前後綴信息，以及它的子串的公共前後綴信息呢？一旦匹配不成功，我怎麼確定匹配字符串的子串移動多少位，恰好靠上後綴呢？
第一個問題，用一個數組就可以維護，這是大家都耳熟能詳的Next數組
Next 數組，Next[i] 表示的是 從 0 開始到 i 結束的子串 的最長公共前後綴的長度 ，咱們舉個栗子就很好理解了。比如下面的字符串 s :
a b a b c a bNext [ 0 ] => a ，只有一個字符，前綴和後綴的概念這裡就不存在了，所以Next [ 0 ] = 0
Next [ 1 ] => a b，前綴 a 不等於後綴 b ，所以也是 0，Next[ 1 ] = 0
Next [ 2 ] => a b a，前綴 a 等於後綴b，但是前綴a b不等於後綴b a ，所以 Next[ 2 ] = 1
Next [ 3 ] => a b a b，前綴 a b等於後綴a b，所以Next[ 3 ] = 3
經過上面的栗子，大概就可以知道 Next 數組是幹嘛的了吧。回到之前的匹配字符串 P：
P a b c x y a b c y 它的 Next 數組是啥呢？看着字符串算法一下就可以得出了
Next[9]= { 0 , 0 , 0 , 0 , 0 , 1 , 2 , 3, 0 } 當我們匹配到第8位，也就是最後一個字符的時候，發現不匹配了
0 1 2 3 4 5 6 7 8 9 10 ↓ S a b c x y a b c x y a P a b c x y a b c y ↑ 於是我們可以直接將 匹配字符串 向右移動 5位，
0 1 2 3 4 5 6 7 8 9 10 | ↓ S a b c x y a b c x y a P a b c x y a b c y | ↑ 0 1 2 3 4 5 6 7 8 這個過程其實就是，當 S [ 8 ] != P [ 8 ] 時 ，S [ 8 ] 直接繼續和 P [ 3 ] 進行比較，依據就是 Next [ 7 ] 的值是 3
因為子串 P[ 0-7 ] 的最大公共前後綴長度是 3，所以S[ 8 ] 只要和 公共前綴的下一個字符P[ Next[ 7 ] ] （Next[ i ] 同樣也是公共前綴的下一個字符的下標，這很好理解）進行比較，也就是 P[ 3 ]，這麼做的的原因是 P[ 0 ],P[ 1 ],P[ 2 ] 和 S[ 5 ] ,S[ 6 ],S[ 7 ] 是公共前後綴，它們都是一樣的！
以上，就是經典 KMP 算法的全部過程。
代碼實現
先是要求 Next[] 數組，怎麼求呢？很簡單，咱們利用動態規劃的思想。Next[ i ]的值要麼是在已有最長公共前後綴的字符串基礎上 +1 ，要麼子串一個符合的都沒有，自己另起爐灶。
Next[ i ] 的值有兩種情況：
- Next [ i – 1 ]不為 0，說明子串 中有公共前後綴，那我就去字符串中公共前綴的下一個字符串 P[ Next [ i-1 ] ]，如果P[ i ] == P [ Next [ i – 1] ]，那麼公共前後綴長度就+1 也就是 Next [ i ] = Next[ i -1 ]+1。那如果不相等呢？那就去找 P [ Next [ i-1 ] ] 的 Next 值，重複上面的過程，有點遞歸的意思。其實這個過程就是在找字符串里的公共前綴，看看有沒有符合條件的（即P [ i ] == P[Next [ k] ]），沒有的話，就在前綴里再去找前綴，直到找到為止，或者發現已經沒用公共前綴了，那就跳出來。
- 發現子串沒有符合條件，讓自己+1的，於是只能從自己開始，看看P[ i ] == P[ 0 ] 如果相等，那就是1 ，如果不相等，那就只能是0 了。
代碼實現如下，理解了其實還是很簡單的，隨時都能手寫出來，也不會忘記。
void getNext(string str) { next[0]=0; for(int i=1;i<str.length();i++) { int k=next[i-1]; while(k!=0&&str[i]!=str[k]) { k=next[k-1]; } if(str[i]==str[k]) next[i]=k+1; else next[i]=0; } } 這就是我對Next 數組的理解，我覺得這樣理解，我能記得住。
還有一種很精簡版的Next 數組實現，我不打算貼出來，亂我心志，我就用我能理解，能看懂的代碼。
Next 數組求出來，就是字符串匹配了。也很簡單哦。
int KMP(string content,string str) { getNext(str); int i=0,j=0; while(i<content.length()&&j<str.length()) { if (j==0 ||content[i]==str[j]) { if(content[i]==str[j]) j++; i++; } else { j=next[j-1]; } } if(j>=str.length()) { return i-str.length(); } else return -1; } j = next [j-1] 就是我上面所有的，移動的過程，其他的也很好理解的。
然後可以用KMP 去通過LeetCode 的一道題目，以檢測自己寫的代碼是否正確：https://leetcode.com/problems/implement-strstr/
總結
KMP 算法就介紹到這裡了，關於KMP 還有很多升級的版本。
字符串快速匹配，第一彈，看毛片。回顧一下，感覺以後應該都不會忘記了吧。
開頭說的 把 KMP 和C#的 String.Contains 進行PK ,要留到下一篇博文里。下一篇博文將對 字符串的匹配的性能來個大排序，並且見識一下微軟的黑科技。
