來了,字串匹配演算法
Live each day like it could be your last.
引言
大道至簡,我的理想是用最簡單的程式碼實現最美的演算法。字串匹配的應用非常廣泛,java的indexOf(),js的全家桶一套匹配(find,indexOf,include...)等等。本文主要分享了它們底層依賴的字串匹配演算法。兩種簡單,兩種複雜。話不多說,所有原始碼均已上傳至github: 連結
BF演算法
bf演算法俗稱樸素匹配演算法,為什麼叫這個名字呢,因為很暴力,在主串中,檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串,看有沒有跟模式串匹配的。
解析
在這裡i迴圈是跟蹤主串txt,j是跟蹤模式串pattern,首先外圍先確定訪問次數,tLen-pLen。
j迴圈來進行比較,這裡可能唯一比較不好理解的是i + j,檢視測試結果,應該可以明白。
private int bfSearch(String txt, String pattern) { int tLen = txt.length(); int pLen = pattern.length(); if (tLen < pLen) return -1; for (int i = 0; i <= tLen - pLen; i++) { int j = 0; for (; j < pLen; j++) { System.out.println(txt.charAt(i + j) + " -- " + pattern.charAt(j)); if (txt.charAt(i + j) != pattern.charAt(j)) break; } if (j == pLen) return i; } return -1; }複製程式碼
變體
bf演算法還有一個變化,用到了顯示回退的思想,i,j的作用和常規的一樣,這裡的i相當於常規的i+j,只不過當發現不匹配的時候,需要回退i和j這兩個指標,j重新回到開頭,i指向下一個字元。
private int bfSearchT(String txt, String pattern) { int tLen = txt.length(); int i = 0; int pLen = pattern.length(); int j = 0; for (; i < tLen && j < pLen; i++) { System.out.println(txt.charAt(i) + " -- " + pattern.charAt(j)); if (txt.charAt(i) == pattern.charAt(j)) { ++j; } else { i -= j; j = 0; } } if (j == pLen) { System.out.println("end... i = " + i + ",plen = " + pLen); return i - pLen; } return -1; }複製程式碼
測試程式碼
ps: hello world
public static void main(String[] args) { BFArithmetic bf = new BFArithmetic(); String txt = "hello world"; String pattern = "world"; int res = bf.bfSearch(txt, pattern); System.out.println("BF演算法匹配結果:" + res); //int resT = bf.bfSearchT(txt, pattern); //System.out.println("BF演算法(顯示回退)匹配結果:" + resT); }複製程式碼
測試結果
RK演算法
rk演算法相當於bf演算法的進階版,它主要是引入了雜湊演算法。降低了時間複雜度。通過雜湊演算法對主串中的 n-m+1 個子串分別求雜湊值,然後逐個與模式串的雜湊值比較大小。如果某個子串的雜湊值與模式串相等,那就說明對應的子串和模式串匹配了。因為雜湊值是一個數字,數字之間比較是否相等是非常快速的,所以模式串和子串比較的效率就提高了。
初始化
這裡要把模式串預製進去,生成相對應的hash值,然後隨機生成一個大素數,便於後續的使用。
private RKArithmetic(String pattern) { this.pattern = pattern; pLen = pattern.length(); aLen = 256; slat = longRandomPrime(); System.out.println("隨機素數:" + slat); aps = 1; // aLen^(pLen - 1) % slat for (int i = 1; i <= pLen - 1; i++) { aps = (aLen * aps) % slat; } patHash = hash(pattern, pLen); System.out.println("patHash = " + patHash); }複製程式碼
準備
隨機生成一個大素數
private static long longRandomPrime() { BigInteger prime = BigInteger.probablePrime(31, new Random()); return prime.longValue(); }複製程式碼
雜湊演算法
private long hash(String txt, int i) { long h = 0; for (int j = 0; j < i; j++) { h = (aLen * h + txt.charAt(j)) % slat; } return h; }複製程式碼
校驗字串是否匹配
private boolean check(String txt, int i) { for (int j = 0; j < pLen; j++) if (pattern.charAt(j) != txt.charAt(i + j)) return false; return true; }複製程式碼
實現
該實現還是比較容易閱讀的,只不過將比較換成了hash值的比較。
private int rkSearch(String txt) { int n = txt.length(); if (n < pLen) return -1; long txtHash = hash(txt, pLen); if ((patHash == txtHash) && check(txt, 0)) return 0; for (int i = pLen; i < n; i++) { txtHash = (txtHash + slat - aps * txt.charAt(i - pLen) % slat) % slat; txtHash = (txtHash * aLen + txt.charAt(i)) % slat; int offset = i - pLen + 1; System.out.println("第" + offset + "次txtHash = " + txtHash); if ((patHash == txtHash) && check(txt, offset)) return offset; } return -1; }複製程式碼
測試程式碼
public static void main(String[] args) { String pat = "world"; String txt = "hello world"; RKArithmetic searcher = new RKArithmetic(pat); int res = searcher.rkSearch(txt); System.out.println("RK演算法匹配結果:" + res); }複製程式碼
測試結果
KMP演算法
未完待續...
BM演算法
未完待續...
end
您的點贊和關注是對我最大的支援,謝謝!