在許多數(shù)據(jù)結(jié)構(gòu)與算法（DSA）問題中，一個(gè)常見任務(wù)是比較字符串——無論是在句子中尋找單詞、檢測重復(fù)詞，還是檢查較大文本中的模式。
可以把這想象成在一大段文字里找一個(gè)短語——手動(dòng)檢查每個(gè)字符會(huì)很累。電腦也是這樣，如果不小心，長文本會(huì)變得非常慢。
參考編程資源
https://pan.quark.cn/s/7f7c83756948
參考
https://pan.quark.cn/s/bda57957c548
這正是Rabin-Karp算法發(fā)揮作用的地方。
它由Michael Rabin和Richard Karp于1987年開發(fā)，作為一種巧妙的方法，利用哈希技術(shù)加快模式匹配。它不是逐個(gè)比較字符，而是將字符串轉(zhuǎn)換成數(shù)字（哈希）并進(jìn)行比較——就像商店里用條形碼而不是讀取完整產(chǎn)品名稱一樣。
簡而言之，拉賓-卡普是：
字符串匹配算法
使用滾動(dòng)哈希來查找文本中所有模式的出現(xiàn)
針對(duì)需要多圖案或重復(fù)匹配的情況進(jìn)行了優(yōu)化
這為許多現(xiàn)代算法在抄襲檢測、子字符串搜索等領(lǐng)域奠定了基礎(chǔ)。
目錄
為什么需要拉賓-卡普？
拉賓-卡普的關(guān)鍵思想
實(shí)用示例以更好地理解
拉賓-卡普的局限性
需要雙哈希
Rabin-Karp 能解決的問題類型
為什么需要拉賓-卡普？
假設(shè)你想查找“代碼”這個(gè)詞是否出現(xiàn)在一篇大文章中。
最簡單的方法？從第一個(gè)字母開始，逐一檢查每組4個(gè)字母。這被稱為“天真方法”，效果不錯(cuò)——但它每次都要檢查每個(gè)字符，如果文本較長，這會(huì)非常緩慢。
樸素方法的時(shí)間復(fù)雜度為O（n × m），其中：
n = 文本長度
m = 圖案長度
現(xiàn)在想象一下，試圖找出多個(gè)模式（比如檢查一份文檔中的100個(gè)不同單詞）。用天真的方式做這件事會(huì)變得非常緩慢。
Rabin-Karp 通過使用滾動(dòng)哈希改進(jìn)了這一點(diǎn)。
它不是每次都比較實(shí)際字符，而是將模式和文本部分轉(zhuǎn)換成數(shù)字（哈希值），然后對(duì)這些數(shù)字進(jìn)行比較。這樣，大多數(shù)情況下它能在不看每個(gè)角色的情況下檢測不匹配，從而更快且可擴(kuò)展。
拉賓-卡普的關(guān)鍵思想
Rabin-Karp的核心思想是將字符串轉(zhuǎn)換為數(shù)值哈希，這樣我們就能比較數(shù)字而非字符。這大大加快了整個(gè)過程。
為了高效實(shí)現(xiàn)這一點(diǎn)，我們使用滾動(dòng)哈希，通過更新上一個(gè)哈希，使我們能在常數(shù)時(shí)間內(nèi)計(jì)算下一個(gè)子串的哈希值。所以我們不再重新檢查每個(gè)字符，而是滑動(dòng)窗口調(diào)整哈希值。
我們先計(jì)算該模式的哈希值，然后將其與文本所有子串的哈希值進(jìn)行比較。如果哈希匹配，我們會(huì)逐字符快速檢查以確認(rèn)（以避免哈希碰撞導(dǎo)致的錯(cuò)誤）。
這樣，大多數(shù)比較都是用數(shù)字完成的，使模式匹配變得快速且可擴(kuò)展，尤其是對(duì)于大型文本或多個(gè)圖案。
在Rabin-Karp中，哈希值是如何計(jì)算的？
Rabin-Karp 中的哈希值是通過滾動(dòng)哈希函數(shù)計(jì)算的，這使得哈希值在圖案滑動(dòng)文本時(shí)能夠高效地更新。滾動(dòng)哈希讓我們不必為每個(gè)子串重新計(jì)算整個(gè)哈希，而是可以移除舊字符的貢獻(xiàn)，并在常數(shù)時(shí)間內(nèi)添加新的字符。
字符串通過多項(xiàng)式滾動(dòng)哈希轉(zhuǎn)換為數(shù)值哈希。對(duì)于長度為 n 的字符串 s，哈希值計(jì)算為：
=>哈希（s） = （s[0] * p（n-1）+ s[1] * p（n-2）+ ... + s[n-1] * p0） %mod
其中：
S[i] 是第i個(gè)字符的數(shù)值（'a' = 1， 'b' = 2， ...， 'z' = 26）
p 是一個(gè)小質(zhì)數(shù)（通常為 31 或 37）
Mod 是一個(gè)較大的質(zhì)數(shù)（比如 1E9 + 7），以避免溢出并減少哈希碰撞
這種方法允許我們利用預(yù)計(jì)算的冪和前置哈希在常數(shù)時(shí)間內(nèi)計(jì)算子串的哈希值。
哈希遞歸關(guān)系
設(shè) preHash[i] 表示前綴子串 s[0...i] 的哈希值。
則遞歸為：preHash[i] = preHash[i - 1] * base + s[i]
其中：
p[0] = s[0]
S[i] 是第i個(gè)字符的數(shù)值（'a' = 1， 'b' = 2， ...， 'z' = 26）
底數(shù)是選定的質(zhì)數(shù)（通常為31或37）
所有作都在模 mod 下進(jìn)行，以避免溢出
如何從L到R計(jì)算哈希值？
要得到任意子串 s[L... 的哈希值R] 高效地使用前綴哈希。
首先，我們預(yù)計(jì)算前綴哈希，其中前綴[i]存儲(chǔ)子字符串s[0...i]的哈希值。同時(shí)，我們還預(yù)先計(jì)算了基數(shù)的冪（如基數(shù)1、基數(shù)2等），以便快速計(jì)算。
然后，利用模運(yùn)算，我們可以用以下公式在常數(shù)時(shí)間內(nèi)計(jì)算任意范圍的哈希值：
hash（L， R） = （前綴[R] - 前綴[L-1] * power（R - L + 1） + mod） % mod
這里，
前綴[R]是從0到R的哈希值
前綴[L-1] * 冪（R - L + 1）去除前L字符的貢獻(xiàn)
- mod 確保結(jié)果保持正值，然后再應(yīng)用 % 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;
}
}
時(shí)間復(fù)雜度：O（n），前綴哈希和冪在字符串的單次處理中預(yù)先計(jì)算完成，耗時(shí)線性時(shí)間。一旦構(gòu)建完成，任何子字符串哈希都可以在 O（1） 時(shí)間內(nèi)檢索。
輔助空間：O（n），兩個(gè)大小為n的數(shù)組用于存儲(chǔ)基的前綴哈希和冪次，導(dǎo)致線性額外空間使用。
實(shí)用示例以更好地理解
給定兩個(gè)字符串：文本（文本）和模式（模式），由小寫英文字母表組成，找到所有以0為基礎(chǔ)的起始索引，其中模式作為文本中的子字符串出現(xiàn)。
示例：
輸入：text = “geeksforgeeks”，pattern = “geeks”
輸出：[0， 8]
解釋：字符串“geeks”出現(xiàn)在文本索引0和8。
輸入：文本 = “aabaacaadaaba”，模式 = “aaba”
輸出：[0， 9， 12]
解釋：
圖片
用于模式搜索的KMP算法
在樸素字符串匹配算法中，我們逐一檢查文本中每個(gè)大小大小的子字符串是否等于該模式。
與樸素算法類似，Rabin-Karp 算法也檢查每個(gè)子串。但與樸素算法不同，Rabin Karp算法會(huì)將模式的哈希值與當(dāng)前文本子串的哈希值匹配，只有當(dāng)哈希值匹配時(shí)，才會(huì)開始匹配單個(gè)字符。因此，Rabin Karp 算法需要計(jì)算以下字符串的哈希值。
圖案本身
文本中所有長度為 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
時(shí)間復(fù)雜度：O（n + m），我們計(jì)算文本和模式的前綴哈希和冪，O（n + m）。然后，我們將窗口滑過文本，每個(gè)子字符串的哈希值以 O（1） 進(jìn)行比較。
輔助空間：O（n + m），我們存儲(chǔ)文本和模式的前綴哈希和冪數(shù)組，取用 O（n + m） 空間。
拉賓-卡普的局限性
可能發(fā)生哈希碰撞——不同的子串可能擁有相同的哈希值。
需要逐角色檢查以確認(rèn)匹配。
如果不小心處理，存在減量溢流的風(fēng)險(xiǎn)。
性能取決于良好的哈希函數(shù)和素模數(shù)。
與像KMP這樣更簡單的算法相比，常數(shù)因子略高一些。
為什么單哈希會(huì)失敗（哈希碰撞）：
使用單一哈希函數(shù)時(shí)，總有可能兩個(gè)不同的子串產(chǎn)生相同的哈希值。這被稱為哈希碰撞。
為什么會(huì)發(fā)生這種事？
=> 我們計(jì)算的是模大數(shù)的哈希（例如，10^9 + 7）
=> 但由于可能的子串?dāng)?shù)量巨大，不同子串取模后可能會(huì)意外得到相同的哈希。
結(jié)果：如果兩個(gè)不同的子串具有相同的哈希值，算法可能會(huì)錯(cuò)誤報(bào)告匹配（假陽性）。在這種情況下，Rabin-Karp需要驗(yàn)證實(shí)際角色才能確認(rèn)匹配——這會(huì)拖慢性能。
需要雙哈希
為了降低碰撞概率，我們使用雙重哈?！从?jì)算兩個(gè)不同的獨(dú)立哈希值：基值（p1， p2）和模數(shù)（mod1， mod2）
它的幫助：
=> 現(xiàn)在，只有當(dāng)兩個(gè)子串的哈希值相匹配時(shí)，才被視為相等。
=> 兩個(gè)不同子串在兩個(gè)哈希函數(shù)中碰撞的概率極低——大約為1/（mod1 x mod2），幾乎可以忽略不計(jì)。
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;
}
}
時(shí)間復(fù)雜度：O（n），前綴哈希和冪在字符串的單次處理中預(yù)先計(jì)算完成，耗時(shí)線性時(shí)間。一旦構(gòu)建完成，任何子字符串哈希都可以在 O（1） 時(shí)間內(nèi)檢索。
輔助空間：O（n），兩個(gè)大小為n的數(shù)組用于存儲(chǔ)基的前綴哈希和冪次，導(dǎo)致線性額外空間使用。
Rabin-Karp 能解決的問題類型
模式匹配——查找大文本中所有模式的出現(xiàn)
抄襲檢測——通過檢查常見子字符串來比較文檔
多重模式搜索——高效地同時(shí)搜索多個(gè)模式
子字符串比較——使用哈希值快速比較子字符串
回文和DP問題——用于基于哈希的優(yōu)化
檢測重復(fù)子串——查找字符串中的重復(fù)序列
最長的常見前綴/后綴——在常數(shù)時(shí)間內(nèi)使用預(yù)先計(jì)算的哈希值
參考編程資源
https://pan.quark.cn/s/7f7c83756948
參考
https://pan.quark.cn/s/bda57957c548
