32 | 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配
作者：鲁米
- 2023-12-13 北京
本文字数：1811 字
阅读完需：约 6 分钟
我们今天讲的都是一维字符串的匹配方法，实际上，这两种算法都可以类比到二维空间。假设有下面这样一个二维字符串矩阵（图中的主串），借助今天讲的处理思路，如何在其中查找另一个二维字符串矩阵（图中的模式串）呢？
暴力匹配算法（BF）
BF 算法是一种朴素的字符串匹配算法，它的基本思想是在文本串中逐个比较所有可能的子串与目标串是否相等。在二维字符串矩阵中，你可以使用两层嵌套的循环来遍历所有可能的子矩阵，然后逐个比较。
Rabin-Karp 算法
RK 算法利用哈希函数在常数时间内计算子串的哈希值，从而加速匹配过程。在二维字符串矩阵中，你可以设计类似的哈希函数，对每个子矩阵计算哈希值，然后与目标矩阵的哈希值比较。
public class StringMatchBKRK {
public static void main(String[] args) { char[][] matrix = { {'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'} };
char[][] target1 = { {'H', 'I'}, {'M', 'N'} };
char[][] target2 = { {'B', 'C'}, {'G', 'H'}, };
StringMatchBKRK matchBKRK = new StringMatchBKRK();
System.out.println("BF Algorithm:"); System.out.println("Target1 Found: " + matchBKRK.searchMatrixBF(matrix, target1)); System.out.println("Target2 Found: " + matchBKRK.searchMatrixBF(matrix, target2));
System.out.println("\nRK Algorithm:"); System.out.println("Target1 Found: " + matchBKRK.searchMatrixRK(matrix, target1)); System.out.println("Target2 Found: " + matchBKRK.searchMatrixRK(matrix, target2)); }
public boolean searchMatrixBF(char[][] matrix, char[][] target) { int m = matrix.length; int n = matrix[0].length; int p = target.length; int q = target[0].length;
for (int i = 0; i <= m - p; i++) { for (int j = 0; j <= n - q; j++) { if (match(matrix, target, i, j)) { return true; } } }
return false; } private boolean match(char[][] matrix, char[][] target, int startRow, int startCol) { int p = target.length; int q = target[0].length;
for (int i = 0; i < p; i++) { for (int j = 0; j < q; j++) { if (matrix[startRow + i][startCol + j] != target[i][j]) { return false; } } } return true; }
public boolean searchMatrixRK(char[][] matrix, char[][] target) { int m = matrix.length; int n = matrix[0].length; int p = target.length; int q = target[0].length;
long targetHash = calculateHash(target);
for (int i = 0; i <= m - p; i++) { for (int j = 0; j <= n - q; j++) { if (calculateHash(matrix, i, j, p, q) == targetHash) { if (match(matrix, target, i, j)) { return true; } } } }
return false; }
private long calculateHash(char[][] matrix, int startRow, int startCol, int rows, int cols) { long hash = 0; long base = 256; long mod = (long) 1e9 + 7; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { hash = (hash * base + matrix[startRow + i][startCol + j]) % mod; } } return hash; }
private long calculateHash(char[][] matrix) { return calculateHash(matrix, 0, 0, matrix.length, matrix[0].length); }
}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 5
鲁米
关注
生活黑客35 2019-06-11 加入
起点不重要，迭代很重要，就需要保持充分的开放和积累；而信息越充分，结果越可靠，又要求随时调整、不断逼近真相。
评论