java实现Rabin-Karp

Rabin-Karp算法是一种用于字符串模式匹配的快速搜索算法，它基于哈希函数的思想，可以在文本串中查找指定的模式串。在Java中实现Rabin-Karp算法，你需要做以下几个步骤：

1. **计算哈希值**：
- 对模式串（pattern）和文本串（text）计算各自的哈希值。通常会取每个字符的ASCII值（或其他合适的方式，如取模运算），然后乘以一定的质数并加上前一个字符的hash值。

   int[] patternHash = new int[pattern.length() + 1];
   for (int i = 0; i < pattern.length(); i++) {
       patternHash[i] = (pattern.charAt(i) & 0xff) % prime;
       if (i > 0) patternHash[i] += prime * patternHash[i - 1];
   }

2. **构造文本哈希表**：
- 对于文本串的每一个滑动窗口，计算其哈希值，并存储在一个数组或HashMap中。

3. **比较哈希值**：
- 比较模式串的当前哈希值和文本哈希表中的对应值，如果相等，则进一步进行精确匹配；如果不相等，则继续移动模式串到下一个位置，更新哈希值。

4. **精确匹配**：
- 如果哈希值相等，在模式串长度内逐字符比对，检查是否完全匹配。

以下是简单的Java代码示例：

public static boolean search(String text, String pattern, int prime) {
    int patternLen = pattern.length();
    int hashText = 0, hashPattern = 0, w = 0;

    for (int i = 0; i < patternLen; i++) {
        hashPattern = (hashPattern * prime + pattern.charAt(i)) % prime;
        w = (w * prime + text.charAt(i)) % prime;
    }

    for (int i = 0; i <= text.length() - patternLen; i++) {
        if (hashPattern == w && text.substring(i, i + patternLen).equals(pattern)) {
            return true;
        }

        if (i < text.length() - patternLen)
            w = (w * prime + text.charAt(i + patternLen)) % prime;
        else
            w = hashText;

        hashText = (hashText * prime + text.charAt(i)) % prime;
    }
    return false;
}