文章出處：極客時間《數(shù)據(jù)結(jié)構(gòu)和算法之美》-作者：王爭。該系列文章是本人的學(xué)習(xí)筆記。

1文本編輯器中的查找功能怎么實(shí)現(xiàn)

在word中有一個功能：查找某個字符串，將其替換為另一個字符串，就會用到這個功能。
需要新算法的原因是：word可能特別長，BF算法可能性能退化很嚴(yán)重；RK算法需要設(shè)計一個能夠處理所有字符串的哈希函數(shù)，這并不容易。
　　新的算法BM，根據(jù)實(shí)驗(yàn)統(tǒng)計，其性能是KMP的3~4倍。

2算法的核心思想

我們把模式串和主串匹配的過程看做是模式串在主串中不斷向后匹配的過程。當(dāng)遇到不匹配的字符的時候BF和RK都是向后移動一位。那可不可以多移動幾位呢？
　　
　　在例子中主串中的c在模式串中不存在，可以直接將模式串移動到c后面。
　　
　　由現(xiàn)象找規(guī)律。當(dāng)遇到不匹配的字符的時候，有什么規(guī)律可以讓模式串一次移動好幾位呢？
　　BM算法就是在找這種規(guī)律。規(guī)律的核心分為壞字符和好后綴兩個規(guī)則。

2.1 壞字符規(guī)則

我們從模式串的末尾往前倒著匹配，當(dāng)我們發(fā)現(xiàn)某個字符沒法匹配的時候，把這個沒有匹配的字符叫做壞字符(主串中的字符串)。
　　當(dāng)發(fā)生不匹配的時候，我們把壞字符在模式串中出現(xiàn)的位置記為si,如果壞字符在模式串中存在，則找到在模式串中最右邊的位置記為xi，不存在xi=-1。模式串向后移動的位數(shù)：si-xi。
　　
　　我們用數(shù)組bc[i]表示字符i在模式串中出現(xiàn)的位置。當(dāng)模式串中有多個字符i的時候，bc[i]保存的是i的最大位置。這是為了防止過度偏移。
　　在上圖中，當(dāng)再次發(fā)生不匹配的時候bc[a]=0。這時候偏移2-0=2。
　　壞字符規(guī)則代碼部分。

// 數(shù)據(jù)包含的字符范圍private static final int SIZE = 256;private void generateBC(char[] b, int m, int[] bc) {Arrays.fill(bc, -1);for (int i = 0; i < m; i++) {bc[(int) b[i]] = i;}}/*** 使用BM算法，查找字符串b在字符串a(chǎn)中出現(xiàn)的首位置。如果沒有出現(xiàn)，返回-1.* * @param a* @param b* @return*/public int bm(char[] a, char[] b) {int n = a.length, m = b.length;int[] bc = new int[SIZE];generateBC(b, m, bc);int i = 0;while (i <= n - m) {int j = m - 1;while (j >= 0 && a[i + j] == b[j]) {j--;}if (j == -1)return i;int x = j - bc[(int) a[i + j]]; i = i + x;}return -1;}

特殊情況下比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaaa。模式串不但不會向后移動，還會向前走。這是因?yàn)?#xff0c;假設(shè)i=0,j從m-1開始匹配，匹配到j(luò)=0的時候發(fā)生不匹配，壞字符為a，suffix[a]=4，j-suffix[‘a(chǎn)’]=-4，i=i-4。i的值 不斷減小。
　　這個時候就需要第二個規(guī)則了。

2.2 好后綴規(guī)則

模式串和主串已經(jīng)匹配好的部分，叫做好后綴。記為{u}。
　　模式串中可能只有一個好后綴，也有可能包含至少2個好后綴。分兩種情況討論。

2.2.1 模式串中至少包含2個u

　　我們查找{u}，在模式串中是否還有出現(xiàn)。從右向左查找第一個出現(xiàn){u}的匹配串記為{u*}。將{u*}滑動到主串與{u}匹配的位置。也就是不同于好后綴，但是是最后一次出現(xiàn)u的起始位置。

2.2.2 模式串中只有一個u

如果不能在模式串中找到另外一個u，怎么辦？直接滑動到主串{u}的后面，會有過渡滑動的可能性。
　　介紹幾個概念。
　　字符串s的后綴子串是指 與最后一個字符跟 字符串s 對齊的子串，比如 abc 的后綴子串包括 c, bc。前綴子串是指起始字符與字符串s對齊的子串。abc的前綴子串包括a,ab。
　　如果好后綴在模式串中不存在可匹配的子串，那在我們一步一步往后滑動模式串的過程中，只要主串中的{u}與模式串有重合，那肯定就無法完全匹配。但是當(dāng)模式串滑動到前綴與主串中{u}的后綴有部分重合的時候，就有可能會存在完全匹配的情況。
　　所以，針對這種情況，需要考察好后綴的后綴子串，是否存在跟模式串的前綴子串匹配的。
　　
　例如圖中第一次發(fā)生不匹配的時候，模式串位置j=4，對應(yīng)主串位置x=7，好后綴是字符串bc。bc在模式串中只出現(xiàn)了一次。如果我們整體向右移動模式串長度 m(=7)，那就可能錯過一次匹配。因?yàn)樵谶@里好后綴bc，有匹配的前綴子串c。將前綴字符串c和好后綴子串c對應(yīng)起來，再次匹配即可。

2.2.3 好后綴規(guī)則編碼

首先我們總結(jié)好后綴規(guī)則。令{u}=好后綴。
如果模式串中包含另外一個子字符串{u*}={u}，則找到這個這個{u*}的起始位置，移動。

如果模式串中不包含另外一個子字符串{u*}，則找到{u}的最長前綴匹配字符串{v}的起始位置，移動。

先考慮怎么表示一個字符串的后綴。對于所有后綴字符串的結(jié)束字符都是一樣的。我們可以用不同的長度表示后綴字符串 。用數(shù)組suffix[i]表示長度為i的后綴字符串 ，在模式串中出現(xiàn)的起始位置。

用prefix[i]表示長度為i的后綴字符串是否有匹配的前綴子串。

　
　怎么得到這兩個數(shù)組有編碼上的技巧。具體看代碼。

2.3 怎么選擇壞字符和好后綴規(guī)則

我們可以分別計算好后綴和壞字符往后滑動的位數(shù)，然后取兩個數(shù)中最大的，作為模式串往后滑動的位數(shù)。

3 BM代碼實(shí)現(xiàn)

public class BM {// 數(shù)據(jù)包含的字符范圍private static final int SIZE = 256;private void generateBC(char[] b, int m, int[] bc) {Arrays.fill(bc, -1);for (int i = 0; i < m; i++) {bc[(int) b[i]] = i;}}/*** 使用BM算法，查找字符串b在字符串a(chǎn)中出現(xiàn)的首位置。如果沒有出現(xiàn)，返回-1.* * @param a* @param b* @return*/public int bm(char[] a, char[] b) {int n = a.length, m = b.length;int[] bc = new int[SIZE];int[] suffix = new int[m];boolean[] prefix = new boolean[m];generateBC(b, m, bc);generatorGS(b, m, suffix, prefix);int i = 0;while (i <= n - m) {int j = m - 1;while (j >= 0 && a[i + j] == b[j]) {j--;}if (j == -1)return i;int x = j - bc[(int) a[i + j]];int y = 0;if(j < m - 1) {y = moveByGS(b, m, j, suffix, prefix);} i = i + Math.max(x, y);}return -1;}/*** 生成后綴子串完整匹配的位置 后綴子串可匹配的最長前綴子串* * @param b* @param m* @param suffix* @param prefix*/private void generatorGS(char[] b, int m, int[] suffix, boolean[] prefix) {Arrays.fill(suffix, -1);for (int i = 0; i < m - 1; i++) {int k = 0;int j = i;while (j >= 0 && b[j] == b[m - 1 - k]) {j--;k++;suffix[k] = j + 1;}if (j == -1) {prefix[k] = true;}}}/*** 按照好后綴規(guī)則，當(dāng)j位置發(fā)生比匹配的時候應(yīng)該移動幾步* * @param b* @param j* @param suffix* @param prefix* @return*/private int moveByGS(char[] b, int m, int j, int[] suffix, boolean[] prefix) {int k = m - 1 - j;//好后綴長度if(suffix[k] != -1) return j - suffix[k] + 1;for(int r = j+2; r < m; r++) {if(prefix[m - r] == true) {return r;}}return 0;}public static void main(String[] args) {String a = "abcacabdc";String b = "abd";int postion = new BM().bm(a.toCharArray(), b.toCharArray());System.out.println(postion);}}

總結(jié)

以上是生活随笔為你收集整理的算法五——字符串匹配(中)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。