串的兩種模式匹配方式（BF/KMP演算法）
- 2019 年 11 月 6 日
- 筆記
前言
串，又稱作字元串，它是由0個或者多個字元所組成的有限序列，串同樣可以採用順序存儲和鏈式存儲兩種方式進行存儲，在主串中查找定位子串問題（模式匹配）是串中最重要的操作之一，而不同的演算法實現有著不同的效率，我們今天就來對比學習串的兩種模式匹配方式：
- 樸素的模式匹配演算法（Brute-Force演算法，簡稱BF演算法）
- KMP模式匹配演算法
樸素的模式匹配演算法（BF演算法）
BF演算法是模式匹配中的一種常規演算法，它的思想就是：
- 第一輪：子串中的第一個字元與主串中的第一個字元進行比較
- 若相等，則繼續比較主串與子串的第二個字元
- 若不相等，進行第二輪比較
- 第二輪：子串中的第一個字元與主串中第二個字元進行比較……
- 第N輪：依次比較下去，直到全部匹配
圖示說明：
第一輪：
第二輪：
…… 原理一致，省略中間步驟
第五輪：
第六輪：
程式碼實現：
看完文字與圖例講解，我們來動手實現一個這樣的演算法
簡單歸納上面的步驟就是：
主串的每一個字元與子串的開頭進行匹配，匹配成功則比較子串與主串的下一位是否匹配，匹配失敗則比較子串與主串的下一位，很顯然，我們可以使用兩個指針來分別指向主串和子串的某個字元，來實現這樣一種演算法
匹配成功，返回子串在主串中第一次出現的位置，匹配失敗返回 -1，子串是空串返回 0
int String::bfFind(const String &s, int pos) const { //主串和子串的指針，i主串，j子串 int i, j; //主串比子串小，匹配失敗，curLenght為串的長度 if (curLength < s.curLenght) return -1; while (i < curLength && j < s.curLength) { //對應字元相等，指針後移 if (data[i] == s.data[j]) i+, j++; else { //對應字元不相等 i = i -j + 1; //主串指針移動 j = 0; //子串從頭開始 } //返回子串在主串的位置 if (j >= s.curLength) return (i - s.curLength); else return -1; } }
註：程式碼只為體現演算法思路，具體定義未給出
這種演算法簡單易懂，卻存在著一個很大的缺點，那就是需要多次回溯，效率低下，若主串為 000000000001 子串為00001，這就意味著每一輪都要比較到子串的最後一個字元才會匹配失敗，有沒有更好的辦法呢？下面的KMP模式匹配演算法就很好的解決了這一問題
KMP模式匹配演算法
如果僅僅進行一些少量數據的運算，可能你甚至覺得BF演算法也還行，起碼是很容易寫出來的，畢竟能跑的就是好程式，但是一旦數據量增大，你就會發現有一些 「無用功」 真的會大大的拖慢你的速度
KMP模式配演算法是由 D.E.Knuth，J.H.Morris，V.R.Pratt 三位前輩提出的，它是一種對樸素模式匹配演算法的改進，核心就是利用匹配失敗後的資訊，盡量減少子主串的匹配次數，其體現就是 主串指針一直往後移動，子串指針回溯
圖示說明：
下面所表示的是樸素模式匹配演算法的過程，我們看看如果使用KMP演算法的思想，哪些步驟是可以省略掉的
① 中前五個元素，均互相匹配，知道第六個元素才匹配失敗，按照BF演算法來說，就直接進行 ② ③ 操作，但是，我們可以發現，子串中的前三個元素 a b c 均不是相同的，但是在 ① 中已經與 主串相匹配，所以 子串分別與主串中的第二 第三個元素匹配 一定是不匹配的，所以圖中的 ② ③ 均可以省略
在 ① 中 子串中的 第一第二個元素 ab 和第四第五個元素 ab 是相同的，且 第四第五個元素 ab 已經與主串中的 第四第五個元素匹配成功，這意味著，子串中第一第二個元素 ab 一定與 主串中 第四第五個元素相匹配，所以 ④ ⑤ 步驟可以省略
如果按照這種思路，上面的例子只需要執行 ① 和 ⑥ 就可以了
next 數組值推導
(一) 主串指針是否需要回溯
我們觀察上面的兩種過程 ，BF演算法-①②③④⑤⑥，KMP演算法-①⑥，如果我們現在假定有兩個指針，i 和 j，分別指向主串和子串中的所處位置，從上圖我們可以知道，主串指針，也就是 i 的值在 ① 的狀態下， 指針指向6的位置，而在 ②③④⑤ 中卻分別指向了2345，而在 ⑥ 中仍指向6的位置
這說明，樸素模式匹配演算法，主串的 i 值會不斷的進行回溯，但是 KMP模式匹配演算法將這種沒必要的回溯省略掉了，所以減少了執行次數
(二) 子串指針優化總結
既然主串指針不進行回溯，那麼還可以優化的就是 子串指針了，一般會遇到兩種情況 我們舉兩個例子：
- 如果子串為 abcdef，主串為abcdexabcdef，當第一輪匹配到第六個字元f和x的時候，匹配失敗了，這個時候如果按照樸素模式匹配，就需要拿子串的首元素a去分別和主串的bcde進行比較，但是由於子串f元素前的元素中沒有相同的元素，並且與主串匹配，所以a與主串中的2-5號元素 即 bcde 都是不可能相匹配的，所有這幾部都可以省略，直接讓a和主串中的x去匹配
- 如果子串為abcabx，主串為abcababcax，在第一輪中，前五個元素子主串分別相匹配，第六個元素位置出錯，按照樸素模式匹配，我們需要拿子串首元素a，依次與主串中的a後面的元素匹配，但是子串前面三個字元abc是不相等的，按照我們第一種情況的經驗，就直接跳過這些步驟了，所有我們直接拿 子串a與 主串第四個元素a進行比較就可以了，但是我們發現，子串中出錯的位置x前的串 abcab 的前綴和後綴都是 ab，既然第一輪的時候，已經匹配成功，那就意味著，子串中的 第一第二個元素ab一定與 主串中 第四第五個元素 ab相等，所以這個步驟也可以省略，也就直接可以拿子串前綴ab後面的c開始於a進行比對，這也就是我們上面圖中例子的詳細思路
總結：所以我們得出規律，子串指針的值取決於，子串前後綴元素的相似程度
想要應用到具體程式碼中，我們可以把子串位置變化 的 j 值定義成一個next數組，且長度與子串長度相同
- 情況1：當 j = 0 時，next[j] = -1, 表示子串指針指向下標為0的元素的時候匹配失敗，子串無法回溯，(j不能賦值-1) ，此時將主串指針後移一位，子串不，進行下一輪比較
- 情況2：在已經匹配的子串中，存在相同的前綴串 T0 T1 … Tk-1 和後綴串 Tj-k Tj-k+1 … Tj-1，子串指針則回溯到next[j] = k的位置，然後進行下一趟比較，例如：子串 abcabc 有相同前綴和後綴ab 所以子串指針回溯到 c的位置
- 情況3：在已經匹配的子串，若不存在相等的前綴和後綴，則主串指針不動，子串指針回溯到 j = 0 的位置，然後進行下一趟比較
例：主串 S = 「abc520abc520abcd」, 子串 T = "abc520abcd" ，利用 KMP演算法匹配過程
子串 next 數組
|
j |
0 1 2 3 4 5 6 7 8 9 |
|---|---|
|
子串 |
a b c 5 2 0 a b c d |
|
next[j] |
-10 0 0 0 0 0 1 2 3 |
可以看到，在 指針 i = 9 且 j = 9 的時候，匹配失敗， 此時 next[9] = 3 ，所以子串指針回溯到 下標 j = 3 的位置也就是元素 5 的位置，進行第二輪比較，然後正好全部匹配成功
(三) 求next數組演算法實現
void Stirng::getNext(const String &t, int *next) { int i = 0, j = -1; next[0] = -1; while (i < t.curLength - 1) { if ((j == -1) || t[i] == t[j]) { ++i, ++j; next[i] = j; }else{ j = next[j]; } } }
KMP演算法程式碼實現
有了 next 數組的鋪墊，我們就可以來實現KMP演算法了
匹配成功返回子串在主串中第一次出現的位置，失敗返回-1，子串為空串返回0
int String::kmpFind(const String &t, int pos) { //不允許申請大小為0的數組 if (t,curLength == 0) return 0; //如果主串比子串小，匹配失敗 if(t.curLength < t.curLength) return -1; //主串指針i，子串指針j int i = 0, j = 0; int *next = new int[t.curLrngth]; getNext(t,next); while (i < curLength && j < t,curLength) { if (j == -1 || data[i] == t.data[j]) //情況12 i++, j++; else //情況3 j = next[j]; } delete []next; if (j > t.curLength) return (i - t.curLength) else return -1; }
KMP模式匹配演算法改進
有一種特殊情況的出現，使得我們不得不考慮KMP演算法的改進
那就是子串中有多個連續重複的元素，例如主串 S=「aaabcde」 子串T=「aaaaax」 在主串指針不動，移動子串指針比較這些值，其實有很多無用功，因為子串中前5個元素都是相同的a，所以我們可以省略掉這些重複的步驟
void String::getNextVal(const String &t, int *nextVal) { int i = 0, j = -1; nextVal[0] = -1; while (i < t.curLength -1) { if ((k == -1) || (t[i] == t[j])) { ++i, ++j; if (t[i] != t[j]) nextVal[i] = j; else nextVal[i] = nextVal[j]; } else j = nextVal[j]; } }
這種改進的核心就在於 增加了對子串中 t[i] 和 t[j] 是否相等的判斷，相等則直接將 nextVal[j] 的值賦給 nextVal[i]
總結
在BF演算法中，當主串和子串不匹配的時候，主串和子串你的指針都需要回溯，所以導致了該演算法時間複雜度比較高為 O(nm) ，空間複雜度為 O(1) 註：雖然其時間複雜度為 O(nm) 但是在一般應用下執行，其執行時間近似 O(n+m) 所以仍被使用
KMP演算法，利用子串的結構相似性，設計next數組，在此之上達到了主串不回溯的效果，大大減少了比較次數，但是相對應的卻犧牲了存儲空間，KMP演算法 時間複雜度為 O(n+m) 空間複雜度為 O(n)
