演算法之字元串模式匹配

導讀

字元串模式匹配是常見的演算法之一，在實際生活中有較高的使用頻率。本文詳細介紹兩種最常見的字元串模式匹配演算法：

• 樸素模式匹配

• KMP模式匹配

字元串模式匹配，也稱子串的定位操作，通俗的說就是在一個主串中判斷是否存在給定的子串（又稱模式串），若存在，則返回匹配成功的索引。如：

主串：zhuanlanzhihu

子串：zhihu

主串中包含子串"zhihu"，說明匹配成功，且返回的索引為：8

注：本文所有出現的字元串的下標都是從0開始標記，並用Java語言實現演算法。

樸素模式匹配

串的樸素模式匹配演算法也稱為BF(Brute-Force)演算法，其基本思想是：從主串的第一個字元起與子串的第一個字元進行比較，若相等，則繼續逐對字元進行後續的比較；若不相等，則從主串第二個字元起與子串的第一個字元重新比較，以此類推，直到子串中每個字元依次和主串中的一個連續的字元序列相等為止，此時稱為匹配成功。如果不能在主串中找到與子串相同的字元序列，則匹配失敗。BF演算法是最原始、最暴力的求解過程，但也是其他匹配演算法的基礎。下面通過具體Demo演示該演算法的基本思想。

主串：zhihzhiuzhihu

子串：zhihiu

注：綠顏色代表匹配成功的字元，紅顏色代表匹配失敗的字元

首先，將主串的第一個字元與子串的第一個字元進行比較，即主串中的第一個字元"z"與子串的第一個字元"z"進行比較，二者相等，依次繼續比較，主串第一個字元後面的"h"、 "i" 、"h"分別與子串第一個字元後面的"h" 、"i"、 "h"進行比較，都分別對應相等，繼續比較主串的"z"與子串的"u"，因為"z"與"u"不相等，則趟匹配失敗。

這時，將主串的指針回溯到第一次比較開始字元的下一個字元即"h"，子串從第一個字元"z"與"h"比較，"z"與"h"不相等，進行下一趟比較。

同理依次比較，主串的"i"與"z"不相等，本趟匹配失敗。繼續從主串的下一個字元"h"與子串的第一個字元"z"進行比較，"h"與"z"不相等，本趟匹配失敗。

同理，繼續從主串的下一個字元"z"與子串的"z"比較，相等，繼續逐次對應比較，"h"與"h"相等，"i"與"i"相等，但後面的對應的"u"與"h"不相等，匹配再次失敗。

主串需要回溯到"z"的下一個字元"h"處，子串從頭來繼續匹配，即"h"與"z"不相等；主串的下一個字元繼續與子串第一個字元比較，即"i"與"z"比較不相等；主串的下一個字元繼續與子串第一個字元比較，即"u"與"z"不相等。

最後，主串的下一個字元"z"與子串的第一個字元"z"比較相等，繼續逐次比較，這時發現對應相同位置的字元都相等，至此，在主串中成功匹配子串，並且位置為：8

根據演算法的基本思想，編寫完整的BF代碼，為了方便起見，測試使用main()方法。

import java.util.Scanner;public class BF { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Please input main string:"); String mainString = scanner.nextLine();// 從標準輸入讀取主串 System.out.println("Please input sub string:"); String subString = scanner.nextLine();// 從標準輸入讀取子串 scanner.close(); BF.match(mainString, subString); } /** * @param s * 主串 * @param t * 子串 */ public static void match(String s, String t) { int index = 0;// 成功匹配的位置 int sLength = s.length();// 主串長度 int tLength = t.length();// 子串長度 if (sLength < tLength) { System.out.println("Error.The main string is greater than the sub string length."); return; } int i = 0; int j = 0; while (i < sLength && j < tLength) { if (s.charAt(i) == t.charAt(j)) {// 判斷對應位置的字元是否相等 i++;// 若相等，主串、子串繼續依次比較 j++; } else {// 若不相等 i = i - j + 1;// 主串回溯到上次開始匹配的下一個字元 j = 0;// 子串從頭開始重新匹配 } } if (j >= tLength) {// 匹配成功 index = i - j; System.out.println("Successful match,index is:" + index); } else {// 匹配失敗 System.out.println("Match failed."); } }}

測試結果：

KMP模式匹配

KMP模式匹配演算法，是一個效率非常高的字元串匹配演算法。其全稱是Knuth–Morris–Pratt string searching algorithm，是由三個人於1977年共同發表的，其中就有他：

他是誰呢？他就是高德納(Donald Ervin Knuth)，堪稱計算機科學理論與技術的經典巨著《計算機程序設計的藝術》的作者，這本書被《美國科學家》雜誌列為20世紀最重要的12本物理科學類專著之一，與愛因斯坦《相對論》、狄拉克《量子力學》、理查·費曼《量子電動力學》等經典比肩而立，他也榮獲1974年度的圖靈獎。閑話少說，回歸正題。在學習KMP演算法之前需要明白什麼是字元串的前綴、後綴，以及前後綴相同元素長度概念。

前綴：指字元串中除了最後一個字元以外，其餘字元的全部頭部順序組合。

後綴：指字元串中除了第一個字元以外，其餘字元的全部尾部順序組合。

前後綴相同元素長度：指字元串所有的前綴與後綴字元依次相同的長度。

首先，KMP演算法是對傳統BF演算法的改善，怎麼改善的呢？在BF演算法中，每當主串與子串對應位置的字元匹配失敗時，主串的位置指針就往前回溯，子串位置指針從頭開始，然後重新匹配。實質上，每當匹配失敗時可以得出兩個結論：

• 本趟匹配失敗
• 子串當前匹配失敗字元之前的字元是匹配成功的

BF演算法正是沒有利用第二條結論的信息，所以效率低。而KMP演算法充分利用了第二條結論的信息，從而避免一些明顯不合法的移位，加快匹配過程。如：

當"D"與"A"匹配失敗，按照BF演算法是不假思索的把子串整體右移一位，主串不動，然後再逐次對應比較。而KMP演算法的核心思想是儘可能的讓子串向右遠移，每次匹配失敗後子串向右移動越遠，比較的次數減少了，演算法的性能自然就提高了。

先看子串的子串的各個前綴後綴的最大相同元素長度分別為：

那麼究竟如何判斷每次匹配失敗後子串需要儘可能地右移多少位呢？這時，我們觀察子串失配位置前的字元，也就是：ABDAB這部分，ABDAB的前後綴相同元素是：AB，也就是說ABDAB的前後綴相同元素長度為：2，根據上表可知，失配時，子串向右儘可能遠移的位數為：已匹配字元數 - 失配字元的上一位字元所對應的最大長度值，即需要右移3位，而這比BF演算法每次失配只右移一位少了兩趟的比較，效率顯而易見。這是通過前後綴相同元素長度來判斷的，為了能用演算法實現該過程，需要引入next數組，next數組表示子串當前匹配失敗字元之前的字元串（子串的子串）的前後綴相同元素長度 ，根據上圖，可求得next數組如下：

不難發現，next數組是將前後綴串相同元素長度整體向右移一位，並人為規定next數組的第一個元素值是-1，因為一個字元串的第一個字元的前面不可能有其他字元，所以就不會存在所謂的前後綴相同元素，同理，一個字元串的第二個字元前只有一個字元，並且前綴與後綴只能是字元串的真子集，所以由一個字元構成的字元串是沒有前綴與後綴的，也就是說前後綴相同元素長度為0。即：next[0]=-1，next[1]=0

注：也有人把next[0]規定為0，這並不影響演算法的實現

求出了next 數組後，從而有：每當主串與子串對應字元失配時，子串整體向右移動的最大位數是：失配字元所在的位置 - 失配字元對應的next[]數值

原理說完，接下來就是最核心的內容是如何通過演算法描述next[]數組。

設子串為「p0p1...pm-1」,當子串的字元pj與主串中相應的字元Si不相等時，因其前j個字元（p0p1...pj-1）已經獲得正確匹配，所以若子串中的「p0p1...pk-1」與「pj-kpj-k+1...pj-1」相同，這時讓Si與pk進行比較。所以next[]數組應當為：

根據上述公式，next[]數組的第一個元素值是-1，並且子串當前字元匹配失敗時子串前面已匹配正確的所有字元構成的字元串若沒有沒有共同前後綴（前綴完全與後綴相等），即前後綴相同元素長度為0，即當前匹配失敗的位置的next[]數值為0，所以說白了這裡的other就是指的是匹配失敗時子串的子串沒有相同的前後綴。這裡最難的是公式的中間部分如何求解max（k）,很多博客或書上都是使用兩個變數去求解，讓人難以理解，這裡我用一個變數j去求解。

從左到右求解一個字元串的各個位置的next[]值，每當右移一個字元，新增的字元X（t.charAt(j-1)）需要用到上一個字元B的next[]值，因為B的next[]存放著子串（模式串）的B之前的子串的前後綴相同元素長度，而字元串下標是從0開始的，所以這個長度值在字元串中的指向的是Y(t.charAt(next[j-1])) ，歸根結底next[j]是與next[j-1]有關的。詳細分成這三種情況：

若 t.charAt(next[j-1])==t.charAt(j-1)為真，即上圖中的Y與X相等，則當前的next[j]=next[j-1]+1

若 t.charAt(next[j-1])==t.charAt(j-1)為假，即上圖中的Y與X不相等，這是需要考慮X是否該串的第一個字元相等，若相等，next[j]=1

如果上述的兩種情況都不成立，也就是說子串（模式串）截止到前一個字元的子串沒有共同元素的前後綴，換句話說就是前後綴相同元素長度為0，即next[j]=0

以下是代碼實現next[]數組：

/** * @param t * 要生成next[]數組的字元串，在KMP演算法中是子串（模式串） * @return 給定字元串的next[]數組 */ public static int[] next(String t) { int[] next = new int[t.length()]; next[0] = -1;// 這裡規定next[]第1個元素值為-1 next[1] = 0; int j = 2;// 從給定的字元串的第3個字元(下標從0開始)開始計算next[j]數值 while (j < t.length()) {// 從第三個字元開始逐次求解對應的next[]值 if (t.charAt(next[j - 1]) == t.charAt(j - 1)) {// 判斷Y與X是否相等（X,Y對應上圖，下同） next[j] = next[j - 1] + 1;// 若Y與X相等，當前next[j]為上一個next[]數組值加1 j++;// 開始自增一個字元，準備下一次求解 } else if (t.charAt(0) == t.charAt(j - 1)) {// 若不相等，判斷X與子串（模式串）第一個字元是否相同 next[j] = 1;// 若相同，找到一個長度為1的相同前後綴，即next[j]為1 j++; } else {// 若上述兩個條件都不滿足，即意味著沒有相等的前後綴，即next[j]為0 next[j] = 0; j++; } } return next; }

但是上面的代碼細細思考，會發現一個小小的問題。在while循環內部的if語句判斷時，t.charAt(next[j-1])==t.charAt(j-1) 當next[j-1]正好等於0時，與下面的else if(t.charAt(0)==t.charAt(j-1))是重複判斷的，為了使代碼更精鍊，應該考慮在第一個if判斷語句中添加一個限制條件，即：next[j-1]!=0 這樣組成if (next[j-1]!=0 && t.charAt(next[j - 1]) == t.charAt(j - 1))，這樣我們就完成了用一個變數j算出next[]數組，大功告成。

求解出最關鍵的next[]後，只需要對BF演算法基礎上略加修改，每次匹配失敗時，獲得該位置的next[]數值，將這個數值賦予變數j(子串的指針)即可。這樣就能保證每次匹配失敗後讓子串右移儘可能遠的距離，這也就是KMP演算法的核心所在。

以下是KMP演算法的完整代碼，同樣也是在main()中做了測試：

import java.util.Scanner;/** * @author RunDouble * */public class KMP { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("Please input main string:"); String mainString = scanner.nextLine();// 從標準輸入讀取主串 System.out.println("Please input sub string:"); String subString = scanner.nextLine();// 從標準輸入讀取子串 scanner.close(); KMP.kmp(mainString, subString); } /** * @param t * 要生成next[]數組的字元串，在KMP演算法中是子串（模式串） * @return 給定字元串的next[]數組 */ public static int[] next(String t) { int[] next = new int[t.length()]; next[0] = -1;// 這裡規定next[]第1個元素值為-1 next[1] = 0; int j = 2;// 從給定的字元串的第3個字元(下標從0開始)開始計算next[j]數值 while (j < t.length()) {// 從第三個字元開始逐次求解對應的next[]值 if (next[j - 1] != 0 && t.charAt(next[j - 1]) == t.charAt(j - 1)) {// 判斷Y與X是否相等（X,Y對應上圖，下同） next[j] = next[j - 1] + 1;// 若Y與X相等，當前next[j]為上一個next[]數組值加1 j++;// 開始自增一個字元，準備下一次求解 } else if (t.charAt(0) == t.charAt(j - 1)) {// 若不相等，判斷X與子串（模式串）第一個字元是否相同 next[j] = 1;// 若相同，找到一個長度為1的相同前後綴，即next[j]為1 j++; } else {// 若上述兩個條件都不滿足，即意味著沒有相等的前後綴，即next[j]為0 next[j] = 0; j++; } } return next; } public static void kmp(String s, String t) { int[] next = next(t);// 調用next（String t）方法 int index = 0;// 成功匹配的位置 int sLength = s.length();// 主串長度 int tLength = t.length();// 子串長度 if (sLength < tLength) { System.out.println("Error.The main string is greater than the sub string length."); return; } int i = 0; int j = 0; while (i < sLength && j < tLength) { /* * 如果j = -1， 或者當前字元匹配成功（即s.charAt(i) == t.charAt(j)）， 都令i++，j++ */ if (j == -1 || s.charAt(i) == t.charAt(j)) { i++; j++; } else { /* * 如果j != -1，且當前字元匹配失敗， 則令 i 不變，j = next[j], next[j]即為j所對應的next值 */ j = next[j]; } } if (j >= tLength) {// 匹配成功 index = i - j; System.out.println("Successful match,index is:" + index); } else {// 匹配失敗 System.out.println("Match failed."); } }}

測試結果：

總結

目前所做的字元串模式匹配只是匹配第一個子串出現的位置，要想匹配所有的子串需要對代碼略加修改。最後提一下兩種演算法的時間複雜度。設主串與子串長度分別為m和n，BF演算法在最壞的情況下，每一趟不成功的匹配都是在子串的最後的一個字元與主串中相應的字元匹配失敗，即在最壞情況下時間複雜度為：O（n*m）。最好的情況是，子串所有字元匹配成功之前的所有次不成功匹配都是子串的第一個字元與主串相應的字元不相同，可得O（n+m）。對於KMP演算法的時間複雜度為：O（n）。現在回過頭來看KMP演算法，只要抓住「主串不回溯，子串往遠移」這句話，盡量減少主串與子串的匹配次數以達到快速匹配的目的，問題就能迎刃而解了。具體的實現關鍵在於如何實現一個next[]數組，這個數組本身包含了子串的局部匹配信息。當然還有其他的串的模式匹配演算法，如Boyer-Moore、Rabin-Karp等字元串查找演算法。

到此，本文結束，祝各位新年健康幸福。

推薦閱讀：