当前位置：首页 > article >正文

字符串算法之Rabin-Karp 算法（字符串匹配）详细解读

article 2025/1/28 1:11:35

Rabin-Karp算法是一种高效的字符串匹配算法，特别适用于在文本中查找多个模式串或在大文本中查找子串。它的主要思想是使用哈希函数将模式串和文本串的子串映射到一个数字，然后比较这些哈希值，以此来判断是否存在匹配。Rabin-Karp算法的平均时间复杂度为 O(n+m)，但在最坏情况下，时间复杂度为 O(n⋅m)。

Rabin-Karp算法的基本原理

哈希函数：通过哈希函数将模式串和文本串的子串转换为哈希值。常用的哈希函数是多项式哈希（polynomial hashing），可以使用以下公式：
h(s)=(s[0]×dm−1+s[1]×dm−2+…+s[m−1]×d0)modq
其中：
- s 是字符串
- d 是字符集的大小（例如，ASCII字符集为256）
- m 是模式串的长度
- q 是一个大的素数，用于减少哈希冲突
滑动窗口：在文本串中使用一个长度为 m 的滑动窗口来提取子串，并计算其哈希值。然后将这个哈希值与模式串的哈希值进行比较。
哈希冲突处理：由于不同的字符串可能会产生相同的哈希值（哈希冲突），因此在哈希值匹配时，需要再次逐字符比较，以确认匹配。

Rabin-Karp算法的步骤

计算模式串的哈希值：计算模式串的哈希值。
计算文本串的初始哈希值：计算文本的前 m 个字符的哈希值。
比较哈希值：
- 如果哈希值匹配，则逐字符比较以确认匹配。
- 如果不匹配，则通过滑动窗口向右移动一个字符，并更新哈希值。
重复步骤3，直到文本串的末尾。

Rabin-Karp算法的Java实现

以下是 Rabin-Karp算法的 Java 实现示例：

import java.util.ArrayList;
import java.util.List;

public class RabinKarpAlgorithm {
    private static final int d = 256; // 字符集大小
    private static final int q = 101; // 质数

    // Rabin-Karp字符串匹配算法
    public void rabinKarp(String text, String pattern) {
        int m = pattern.length();
        int n = text.length();
        int p = 0; // 模式串的哈希值
        int t = 0; // 文本串的哈希值
        int h = 1; // h 是 d^(m-1) % q

        // 计算 d^(m-1) % q
        for (int i = 0; i < m - 1; i++) {
            h = (h * d) % q;
        }

        // 计算模式串和文本串的初始哈希值
        for (int i = 0; i < m; i++) {
            p = (d * p + pattern.charAt(i)) % q;
            t = (d * t + text.charAt(i)) % q;
        }

        // 滑动窗口
        for (int i = 0; i <= n - m; i++) {
            // 如果哈希值相等，进一步比较字符
            if (p == t) {
                int j;
                for (j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        break;
                    }
                }
                if (j == m) {
                    System.out.println("Pattern found at index: " + i);
                }
            }

            // 计算下一个窗口的哈希值
            if (i < n - m) {
                t = (d * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;
                // 处理负值
                if (t < 0) {
                    t += q;
                }
            }
        }
    }

    public static void main(String[] args) {
        RabinKarpAlgorithm rabinKarp = new RabinKarpAlgorithm();
        String text = "GEEKS FOR GEEKS";
        String pattern = "GEEK";
        rabinKarp.rabinKarp(text, pattern); // 在文本中查找模式串
    }
}

代码解读

常量定义：
- d：字符集大小（在这里选择为256，即ASCII字符集）。
- q：一个大的素数，用于减少哈希冲突。
rabinKarp 方法：
- 计算模式串的哈希值和文本串的初始哈希值。
- 使用滑动窗口遍历文本串，比较哈希值。如果哈希值相等，进一步逐字符比较以确认匹配。
- 更新哈希值时，使用公式计算下一个窗口的哈希值。
main 方法：创建 RabinKarpAlgorithm 实例，并在给定的文本串中查找指定的模式串。