模式匹配是數據結構中字符串的一種基本運算，給定一個子串，要求在某個字符串中找出與該子串相同的所有子串。假設P是給定的子串，T是待查找的字符串，要求從T中找出與P相同的所有子串，這個問題成為模式匹配問題。P稱為模式，T稱為文本。

這篇文章介紹了蠻力法在字符串匹配問題中的應用（JAVA）--樸素模式匹配算法，沒有基礎的讀者可以先參考這篇文章。

上述的蠻力法求解的思路為：從左到右比較模式和文本中的每一對相應的字符，一旦匹配失敗，模式右移一格，進行下一輪嘗試。這種方法的時間復雜度為O(nm)，實在是不夠高效。

也有一些高效的算法被實現，諸如KMP算法和BM算法，這些算法中大多采用了輸入增強思想（即對模式進行預處理以得到一些信息，將信息存儲到表中，以便在匹配時能夠使用這些信息）。這里將介紹BM算法的一種簡化版本Horspool算法。

Horspool算法每次從右往左對模式串和文本進行匹配，如果出現一對匹配失敗，則將模式串按情況從左往右移動。這里注意匹配的方向和移動的方向是不一樣的。而“按情況”這就是比樸素匹配要高明的地方。

樸素匹配的移動方式，一旦匹配失敗，所有情況都只會右移一個重新匹配。

而對于Horspool算法來說，我們假定文本匹配窗口（指的是文本中當前與模式進行匹配的等長部分，下圖方框中的內容）這里的情況有四種。

情況一：如果匹配串中不包含c（下圖中就是字母S），那么需要將模式串str移動str.length個長度（如果移動的幅度小于str.lengh，那么模式中的其他元素還是會和c對齊，這是沒有意義的操作過程），如下圖：

情況二：如果模式串中包含c，但不是模式的最后一個字符（下圖中就是字母B）,需要將模式串str中最右邊的c與文本中的c對齊（因為該算法的匹配方式是從右往左匹配，這樣能使匹配窗口盡可能的滿足）。

情況三：如果c剛好是模式中的最后一個字符，但在模式的其他m-1個字符中不包含c，移動情況類似于情況一

情況四：如果c剛好是模式中的最后一個字符，但在模式的前m-1個字符中也包含c，移動情況類似于情況二

但是，還有一個重要的問題就是，如果我們每次都要嘗試檢查模式中的每個字符，那該算法也就失去了意義，改進方法就是通過預處理來解決，我們要預先計算除每次移動的距離并存儲在表中，以便查找使用。

Horspool算法思路：

1. 對給定的長度為m的模式和在模式及文本中用到的字母，按照上面的方法構造移動表t[ ]

2. 將模式與文本的開始處對齊

3. 當構成文本匹配窗口后（也就是至少要從開始處移動m長度之后），從模式的最后一個字符開始，比較模式與文本中的相應字符，如全部匹配成功，則終止；如果遇到不匹配的字符，按照t[ ]移動模式。

完整代碼如下：

import java.util.HashMap;public class Main {public static final char[] CHAR_TABLE = { 'a', 'b', 'c', 'd', 'e', 'f','g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's','t', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F','G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S','T', 'U', 'V', 'W', 'X', 'Y', 'Z', '0', '1', '2', '3', '4', '5','6', '7', '8', '9', '(', ')', '{', '}', '[', ']', '<', '>', ',','.', '_', '-', '+', '=', '~', '/', '?', ';', ':', '"', '|', '!','@', '#', '$', '%', '^', '&', '*' };public static HashMap<Character, Integer> ShiftTable(String p) {int m = p.length();HashMap<Character, Integer> table = new HashMap<Character, Integer>();for (int i = 0; i < CHAR_TABLE.length; i++)table.put(CHAR_TABLE[i], m);for (int i = 0; i < m - 1; i++)table.put(p.charAt(i), m - 1 - i);return table;}public static int HorspoolMatching(String p, String t) {HashMap<Character, Integer> table = ShiftTable(p);int m = p.length();int n = t.length();int i = m - 1; // 模式左右邊的位置while (i <= n - 1) {int k = 0;while ((k <= m - 1) && p.charAt(m - 1 - k) == t.charAt(i - k)) {k++;}if (k == m)return i - (m - 1);elsei += table.get(t.charAt(i));}return -1;}public static void main(String[] argv) {String p="AECDE";String t="ZXYABPDEAECDE";System.out.println(HorspoolMatching(p, t));}}

總結

以上是生活随笔為你收集整理的时空权衡在模式匹配算法中的应用（JAVA）--Horspool算法（简化版BM算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。