Search Pattern (Rabin-Karp Algorithm) in Java

Rabin-Karp 算法是一种高效的字符串匹配方法，它使用哈希来在文本中查找模式。它不逐个检查字符，而是计算模式的哈希值，并将其与文本子字符串的哈希值进行比较。当发生哈希匹配时，算法会执行逐字符检查以验证匹配。

示例 1：在句子中查找单词

输入

文本 = "WELCOME TO JAVA PROGRAMMING"

模式 = "JAVA"

输出

模式在索引处找到：11

示例 2：搜索多次出现

输入

文本 = "ABABCABAB"

模式 = "ABAB"

输出

模式在索引处找到：0, 5

如何在 Rabin-Karp 中计算哈希值？

步骤 1：选择基数和模数

选择一个素数 q 作为模数，以最小化哈希冲突并防止溢出。将 d 设置为基数，它表示可能的字符数（例如，ASCII 为 256）。

步骤 2：初始化哈希值

将模式和文本的第一个窗口的初始哈希值均设置为零。

步骤 3：计算模式和文本的初始哈希值

遍历模式和文本的第一个部分，使用以下公式计算它们的哈希值：

步骤 4：在文本中滑动模式

计算文本中第一个子字符串的哈希值，然后将模式一次一个字符地滑过文本。

步骤 5：更新每次滑动的哈希值

对于每次滑动，使用以下公式更新哈希值：

这可以有效地移除移出字符的贡献并添加新字符。

步骤 6：检查匹配

如果子字符串的哈希值与模式的哈希值匹配，则执行逐字符比较以确认匹配，因为不同的子字符串可能会产生相同的哈希值。

顶部表单

底部表单

算法

步骤 1：使用滚动哈希函数计算指定模式和文本初始窗口的哈希值，同时预先计算哈希基数以实现更高效的滑动。

步骤 2：一次将窗口向前移动一个字符，遍历文本，并将当前窗口的哈希值与模式的哈希值进行比较。

步骤 3：当哈希值相同时，对模式和当前文本窗口进行逐字符比较，以验证是否存在合法匹配。

步骤 4：通过消除第一个字符，合并后续字符，并在必要时进行负值调整来计算下一个窗口的哈希值。

步骤 5：继续滑动窗口，查找匹配项，修改哈希值，并显示模式在文本中出现的所有位置。

让我们在 Java 程序中实现上述步骤。

文件名：RabinKarp.java

输出

 
Match found at index: 24   

时间复杂度：由于哈希冲突，最坏情况复杂度为 O(N × M)，而使用高效的滚动哈希计算，平均情况复杂度为 O(N + M)。

辅助空间复杂度：该算法仅需要几个整数变量来进行哈希计算，因此其辅助空间复杂度为 O(1)。