在许多数据结构与算法（DSA）问题中，一个常见任务是比较字符串——无论是在句子中寻找单词、检测重复词，还是检查较大文本中的模式。
可以把这想象成在一大段文字里找一个短语——手动检查每个字符会很累。电脑也是这样，如果不小心，长文本会变得非常慢。
参考编程资源
https://pan.quark.cn/s/7f7c83756948
参考
https://pan.quark.cn/s/bda57957c548
这正是Rabin-Karp算法发挥作用的地方。
它由Michael Rabin和Richard Karp于1987年开发，作为一种巧妙的方法，利用哈希技术加快模式匹配。它不是逐个比较字符，而是将字符串转换成数字（哈希）并进行比较——就像商店里用条形码而不是读取完整产品名称一样。
简而言之，拉宾-卡普是：
字符串匹配算法
使用滚动哈希来查找文本中所有模式的出现
针对需要多图案或重复匹配的情况进行了优化
这为许多现代算法在抄袭检测、子字符串搜索等领域奠定了基础。
目录
为什么需要拉宾-卡普？
拉宾-卡普的关键思想
实用示例以更好地理解
拉宾-卡普的局限性
需要双哈希
Rabin-Karp 能解决的问题类型
为什么需要拉宾-卡普？
假设你想查找“代码”这个词是否出现在一篇大文章中。
最简单的方法？从第一个字母开始，逐一检查每组4个字母。这被称为“天真方法”，效果不错——但它每次都要检查每个字符，如果文本较长，这会非常缓慢。
朴素方法的时间复杂度为O（n × m），其中：
n = 文本长度
m = 图案长度
现在想象一下，试图找出多个模式（比如检查一份文档中的100个不同单词）。用天真的方式做这件事会变得非常缓慢。
Rabin-Karp 通过使用滚动哈希改进了这一点。
它不是每次都比较实际字符，而是将模式和文本部分转换成数字（哈希值），然后对这些数字进行比较。这样，大多数情况下它能在不看每个角色的情况下检测不匹配，从而更快且可扩展。
拉宾-卡普的关键思想
Rabin-Karp的核心思想是将字符串转换为数值哈希，这样我们就能比较数字而非字符。这大大加快了整个过程。
为了高效实现这一点，我们使用滚动哈希，通过更新上一个哈希，使我们能在常数时间内计算下一个子串的哈希值。所以我们不再重新检查每个字符，而是滑动窗口调整哈希值。
我们先计算该模式的哈希值，然后将其与文本所有子串的哈希值进行比较。如果哈希匹配，我们会逐字符快速检查以确认（以避免哈希碰撞导致的错误）。
这样，大多数比较都是用数字完成的，使模式匹配变得快速且可扩展，尤其是对于大型文本或多个图案。
在Rabin-Karp中，哈希值是如何计算的？
Rabin-Karp 中的哈希值是通过滚动哈希函数计算的，这使得哈希值在图案滑动文本时能够高效地更新。滚动哈希让我们不必为每个子串重新计算整个哈希，而是可以移除旧字符的贡献，并在常数时间内添加新的字符。
字符串通过多项式滚动哈希转换为数值哈希。对于长度为 n 的字符串 s，哈希值计算为：
=>哈希（s） = （s[0] * p（n-1）+ s[1] * p（n-2）+ ... + s[n-1] * p0） %mod
其中：
S[i] 是第i个字符的数值（'a' = 1， 'b' = 2， ...， 'z' = 26）
p 是一个小质数（通常为 31 或 37）
Mod 是一个较大的质数（比如 1E9 + 7），以避免溢出并减少哈希碰撞
这种方法允许我们利用预计算的幂和前置哈希在常数时间内计算子串的哈希值。
哈希递归关系
设 preHash[i] 表示前缀子串 s[0...i] 的哈希值。
则递归为：preHash[i] = preHash[i - 1] * base + s[i]
其中：
p[0] = s[0]
S[i] 是第i个字符的数值（'a' = 1， 'b' = 2， ...， 'z' = 26）
底数是选定的质数（通常为31或37）
所有作都在模 mod 下进行，以避免溢出
如何从L到R计算哈希值？
要得到任意子串 s[L... 的哈希值R] 高效地使用前缀哈希。
首先，我们预计算前缀哈希，其中前缀[i]存储子字符串s[0...i]的哈希值。同时，我们还预先计算了基数的幂（如基数1、基数2等），以便快速计算。
然后，利用模运算，我们可以用以下公式在常数时间内计算任意范围的哈希值：
hash（L， R） = （前缀[R] - 前缀[L-1] * power（R - L + 1） + mod） % mod
这里，
前缀[R]是从0到R的哈希值
前缀[L-1] * 幂（R - L + 1）去除前L字符的贡献
- mod 确保结果保持正值，然后再应用 % mod
class GfG {
private final int mod = (int)1e9 + 7;
private final int base = 31;
private int[] hash;
private int[] power;
// modular addition
private int add(int a, int b) {
a += b;
if (a >= mod) a -= mod;
return a;
}
// modular subtraction
private int sub(int a, int b) {
a -= b;
if (a < 0) a += mod;
return a;
}
// modular multiplication
private int mul(int a, int b) {
return (int)((1L * a * b) % mod);
}
// convert character to int
// ('a' = 1, ..., 'z' = 26)
private int charToInt(char c) {
return c - 'a' + 1;
}
// constructor: precomputes prefix hashes and powers
public GfG(String s) {
int n = s.length();
hash = new int[n];
power = new int[n];
hash[0] = charToInt(s.charAt(0));
power[0] = 1;
for (int i = 1; i < n; i++) {
hash[i] = add(mul(hash[i - 1], base), charToInt(s.charAt(i)));
power[i] = mul(power[i - 1], base);
}
}
// get hash of substring s[l...r] in O(1)
public int getSubHash(int l, int r) {
int h = hash[r];
if (l > 0) {
h = sub(h, mul(hash[l - 1], power[r - l + 1]));
}
return h;
}
}
时间复杂度：O（n），前缀哈希和幂在字符串的单次处理中预先计算完成，耗时线性时间。一旦构建完成，任何子字符串哈希都可以在 O（1） 时间内检索。
辅助空间：O（n），两个大小为n的数组用于存储基的前缀哈希和幂次，导致线性额外空间使用。
实用示例以更好地理解
给定两个字符串：文本（文本）和模式（模式），由小写英文字母表组成，找到所有以0为基础的起始索引，其中模式作为文本中的子字符串出现。
示例：
输入：text = “geeksforgeeks”，pattern = “geeks”
输出：[0， 8]
解释：字符串“geeks”出现在文本索引0和8。
输入：文本 = “aabaacaadaaba”，模式 = “aaba”
输出：[0， 9， 12]
解释：
图片
用于模式搜索的KMP算法
在朴素字符串匹配算法中，我们逐一检查文本中每个大小大小的子字符串是否等于该模式。
与朴素算法类似，Rabin-Karp 算法也检查每个子串。但与朴素算法不同，Rabin Karp算法会将模式的哈希值与当前文本子串的哈希值匹配，只有当哈希值匹配时，才会开始匹配单个字符。因此，Rabin Karp 算法需要计算以下字符串的哈希值。
图案本身
文本中所有长度为 m 的子串，也就是模式的大小。
import java.util.ArrayList;
class RabinKarpHash {
private final int mod = 1000000007;
private final int base = 31;
private int[] hash;
private int[] power;
// modular addition
private int add(int a, int b) {
a += b;
if (a >= mod) a -= mod;
return a;
}
// modular subtraction
private int sub(int a, int b) {
a -= b;
if (a < 0) a += mod;
return a;
}
// modular multiplication
private int mul(int a, int b) {
return (int)((1L * a * b) % mod);
}
// convert character to int
// ('a' = 1, ..., 'z' = 26)
private int charToInt(char c) {
return c - 'a' + 1;
}
// constructor: precomputes prefix hashes and powers
public RabinKarpHash(String s) {
int n = s.length();
hash = new int[n];
power = new int[n];
hash[0] = charToInt(s.charAt(0));
power[0] = 1;
for (int i = 1; i < n; ++i) {
hash[i] = add(mul(hash[i - 1], base), charToInt(s.charAt(i)));
power[i] = mul(power[i - 1], base);
}
}
// get hash of substring s[l...r] in O(1)
public int getSubHash(int l, int r) {
int h = hash[r];
if (l > 0) {
h = sub(h, mul(hash[l - 1], power[r - l + 1]));
}
return h;
}
}
class GfG {
// Rabin-Karp search using hash class
public static ArrayList<Integer> searchPattern(String text, String pattern) {
int n = text.length(), m = pattern.length();
RabinKarpHash textHash = new RabinKarpHash(text);
RabinKarpHash patHash = new RabinKarpHash(pattern);
int patternHash = patHash.getSubHash(0, m - 1);
ArrayList<Integer> result = new ArrayList<>();
for (int i = 0; i <= n - m; i++) {
int subHash = textHash.getSubHash(i, i + m - 1);
if (subHash == patternHash) {
result.add(i);
}
}
return result;
}
public static void main(String[] args) {
String txt = "geeksforgeeks";
String pat = "geek";
ArrayList<Integer> positions = searchPattern(txt, pat);
for (int idx : positions) {
System.out.print(idx + " ");
}
System.out.println();
}
}
输出
0 8
时间复杂度：O（n + m），我们计算文本和模式的前缀哈希和幂，O（n + m）。然后，我们将窗口滑过文本，每个子字符串的哈希值以 O（1） 进行比较。
辅助空间：O（n + m），我们存储文本和模式的前缀哈希和幂数组，取用 O（n + m） 空间。
拉宾-卡普的局限性
可能发生哈希碰撞——不同的子串可能拥有相同的哈希值。
需要逐角色检查以确认匹配。
如果不小心处理，存在减量溢流的风险。
性能取决于良好的哈希函数和素模数。
与像KMP这样更简单的算法相比，常数因子略高一些。
为什么单哈希会失败（哈希碰撞）：
使用单一哈希函数时，总有可能两个不同的子串产生相同的哈希值。这被称为哈希碰撞。
为什么会发生这种事？
=> 我们计算的是模大数的哈希（例如，10^9 + 7）
=> 但由于可能的子串数量巨大，不同子串取模后可能会意外得到相同的哈希。
结果：如果两个不同的子串具有相同的哈希值，算法可能会错误报告匹配（假阳性）。在这种情况下，Rabin-Karp需要验证实际角色才能确认匹配——这会拖慢性能。
需要双哈希
为了降低碰撞概率，我们使用双重哈希——即计算两个不同的独立哈希值：基值（p1， p2）和模数（mod1， mod2）
它的帮助：
=> 现在，只有当两个子串的哈希值相匹配时，才被视为相等。
=> 两个不同子串在两个哈希函数中碰撞的概率极低——大约为1/（mod1 x mod2），几乎可以忽略不计。
import java.util.ArrayList;
public class RabinKarpHash {
private final int mod1 = (int) 1e9 + 7;
private final int mod2 = (int) 1e9 + 9;
private final int base1 = 31;
private final int base2 = 37;
private int[] hash1, hash2;
private int[] power1, power2;
// modular addition
private int add(int a, int b, int mod) {
a += b;
if (a >= mod) a -= mod;
return a;
}
// modular subtraction
private int sub(int a, int b, int mod) {
a -= b;
if (a < 0) a += mod;
return a;
}
// modular multiplication
private int mul(int a, int b, int mod) {
return (int) ((1L * a * b) % mod);
}
// convert character to int
private int charToInt(char c) {
return c - 'a' + 1;
}
// constructor: precomputes both prefix hashes and powers
public RabinKarpHash(String s) {
int n = s.length();
hash1 = new int[n];
hash2 = new int[n];
power1 = new int[n];
power2 = new int[n];
hash1[0] = charToInt(s.charAt(0));
hash2[0] = charToInt(s.charAt(0));
power1[0] = 1;
power2[0] = 1;
for (int i = 1; i < n; ++i) {
hash1[i] = add(mul(hash1[i - 1], base1, mod1),
charToInt(s.charAt(i)), mod1);
power1[i] = mul(power1[i - 1], base1, mod1);
hash2[i] = add(mul(hash2[i - 1], base2, mod2),
charToInt(s.charAt(i)), mod2);
power2[i] = mul(power2[i - 1], base2, mod2);
}
}
// get double hash of substring s[l...r]
public ArrayList<Integer> getSubHash(int l, int r) {
int h1 = hash1[r];
int h2 = hash2[r];
if (l > 0) {
h1 = sub(h1, mul(hash1[l - 1], power1[r - l + 1], mod1), mod1);
h2 = sub(h2, mul(hash2[l - 1], power2[r - l + 1], mod2), mod2);
}
ArrayList<Integer> res = new ArrayList<>();
res.add(h1);
res.add(h2);
return res;
}
}
时间复杂度：O（n），前缀哈希和幂在字符串的单次处理中预先计算完成，耗时线性时间。一旦构建完成，任何子字符串哈希都可以在 O（1） 时间内检索。
辅助空间：O（n），两个大小为n的数组用于存储基的前缀哈希和幂次，导致线性额外空间使用。
Rabin-Karp 能解决的问题类型
模式匹配——查找大文本中所有模式的出现
抄袭检测——通过检查常见子字符串来比较文档
多重模式搜索——高效地同时搜索多个模式
子字符串比较——使用哈希值快速比较子字符串
回文和DP问题——用于基于哈希的优化
检测重复子串——查找字符串中的重复序列
最长的常见前缀/后缀——在常数时间内使用预先计算的哈希值
参考编程资源
https://pan.quark.cn/s/7f7c83756948
参考
https://pan.quark.cn/s/bda57957c548
