# Rabin-Karp 算法 > 原文： [https://www.programiz.com/dsa/rabin-karp-algorithm](https://www.programiz.com/dsa/rabin-karp-algorithm) #### 在本教程中，您將學習什么是 rabin-karp 算法。 此外，您還將在 C，C++ ，Java 和 Python 中找到 rabin-karp 算法的工作示例。 Rabin-Karp 算法是一種用于使用哈希函數搜索/匹配文本中的模式的算法。 與樸素的字符串匹配算法不同，它在初始階段不會遍歷每個字符，而是過濾不匹配的字符，然后執行比較。 哈希函數是一種將較大的輸入值映射到較小的輸出值的工具。 此輸出值稱為哈希值。 * * * ## Rabin-Karp 算法如何工作？ 采取一系列字符并檢查是否存在所需字符串。 如果找到了可能性，則執行字符匹配。 讓我們通過以下步驟來了解算法： 1. 假設文本為：  文本 ，并且要在上述文本中搜索的字符串為：  模式 2. 讓我們為問題中要使用的字符分配一個數值（`v`）/權重。 在這里，我們僅采用了前十個字母（即 A 到 J）。  文本權重 3. `m`是模式的長度，`n`是文本的長度。 在此，`m = 10 and n = 3.` 令`d`為輸入集中的字符數。 在這里，我們采用了輸入集`{A, B, C, ..., J}`。 因此，`d = 10`。 您可以為`d`假定任何合適的值。 4. 讓我們計算模式的哈希值。  文本的哈希值 ``` hash value for pattern(p) = Σ(v * dm-1) mod 13 = ((3 * 102) + (4 * 101) + (4 * 100)) mod 13 = 344 mod 13 = 6 ``` 在上面的計算中，選擇質數（此處為 13），以便我們可以使用單精度算術執行所有計算。 [計算模量的原因在之下給出](/dsa/rabin-karp-algorithm#limitations)。 5. 計算大小為`m`的文本窗口的哈希值。 ``` For the first window ABC, hash value for text(t) = Σ(v * dn-1) mod 13 = ((1 * 102) + (2 * 101) + (3 * 100)) mod 13 = 123 mod 13 = 6 ``` 6. 將模式的哈希值與文本的哈希值進行比較。 如果它們匹配，則執行字符匹配。 在上面的示例中，第一個窗口的哈希值（即`t`）與`p`匹配，因此請在`ABC`和`CDD`之間進行字符匹配。 由于它們不匹配，請轉到下一個窗口。 7. 我們通過減去第一項并添加下一項來計算下一個窗口的哈希值，如下所示。 ``` t = ((1 * 102) + ((2 * 101) + (3 * 100)) * 10 + (3 * 100)) mod 13 = 233 mod 13 = 12 ``` 為了優化此過程，我們以以下方式使用先前的哈希值。 ``` t = ((d * (t - v[character to be removed] * h) + v[character to be added] ) mod 13 = ((10 * (6 - 1 * 9) + 3 )mod 13 = 12 Where, h = dm-1 = 103-1 = 100. ``` 8. 對于`BCC`，`t = 12`（`≠ 6`）。 因此，轉到下一個窗口。 經過幾次搜索，我們將在文本中獲得窗口`CDA`的匹配項。  不同窗口的哈希值 * * * ## 算法 ``` n = t.length m = p.length h = dm-1 mod q p = 0 t0 = 0 for i = 1 to m p = (dp + p[i]) mod q t0 = (dt0 + t[i]) mod q for s = 0 to n - m if p = ts if p[1.....m] = t[s + 1..... s + m] print "pattern found at position" s If s < n-m ts + 1 = (d (ts - t[s + 1]h) + t[s + m + 1]) mod q ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Rabin-Karp algorithm in python d = 10 def search(pattern, text, q): m = len(pattern) n = len(text) p = 0 t = 0 h = 1 i = 0 j = 0 for i in range(m-1): h = (h*d) % q # Calculate hash value for pattern and text for i in range(m): p = (d*p + ord(pattern[i])) % q t = (d*t + ord(text[i])) % q # Find the match for i in range(n-m+1): if p == t: for j in range(m): if text[i+j] != pattern[j]: break j += 1 if j == m: print("Pattern is found at position: " + str(i+1)) if i < n-m: t = (d*(t-ord(text[i])*h) + ord(text[i+m])) % q if t < 0: t = t+q text = "ABCCDDAEFG" pattern = "CDD" q = 13 search(pattern, text, q) ``` ```java // Rabin-Karp algorithm in Java public class RabinKarp { public final static int d = 10; static void search(String pattern, String txt, int q) { int m = pattern.length(); int n = txt.length(); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) { p = (d * p + pattern.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; } // Find the match for (i = 0; i <= n - m; i++) { if (p == t) { for (j = 0; j < m; j++) { if (txt.charAt(i + j) != pattern.charAt(j)) break; } if (j == m) System.out.println("Pattern is found at position: " + (i + 1)); } if (i < n - m) { t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q; if (t < 0) t = (t + q); } } } public static void main(String[] args) { String txt = "ABCCDDAEFG"; String pattern = "CDD"; int q = 13; search(pattern, txt, q); } } ``` ```c // Rabin-Karp algorithm in C #include <stdio.h> #include <string.h> #define d 10 void rabinKarp(char pattern[], char text[], int q) { int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) { p = (d * p + pattern[i]) % q; t = (d * t + text[i]) % q; } // Find the match for (i = 0; i <= n - m; i++) { if (p == t) { for (j = 0; j < m; j++) { if (text[i + j] != pattern[j]) break; } if (j == m) printf("Pattern is found at position: %d \n", i + 1); } if (i < n - m) { t = (d * (t - text[i] * h) + text[i + m]) % q; if (t < 0) t = (t + q); } } } int main() { char text[] = "ABCCDDAEFG"; char pattern[] = "CDD"; int q = 13; rabinKarp(pattern, text, q); } ``` ```cpp // Rabin-Karp algorithm in C++ #include <string.h> #include <iostream> using namespace std; #define d 10 void rabinKarp(char pattern[], char text[], int q) { int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) { p = (d * p + pattern[i]) % q; t = (d * t + text[i]) % q; } // Find the match for (i = 0; i <= n - m; i++) { if (p == t) { for (j = 0; j < m; j++) { if (text[i + j] != pattern[j]) break; } if (j == m) cout << "Pattern is found at position: " << i + 1 << endl; } if (i < n - m) { t = (d * (t - text[i] * h) + text[i + m]) % q; if (t < 0) t = (t + q); } } } int main() { char text[] = "ABCCDDAEFG"; char pattern[] = "CDD"; int q = 13; rabinKarp(pattern, text, q); } ``` * * * ## Rabin-Karp 算法的局限性 ### 虛假命中 當模式的哈希值與文本窗口的哈希值匹配，但該窗口不是實際的模式時，則稱為虛假命中。 雜散命中會增加算法的時間復雜度。 為了最小化雜散命中，我們使用模數。 它大大減少了偽造的打擊。 * * * ## Rabin-Karp 算法復雜度 Rabin-Karp 算法的平均情況和最佳情況復雜度為`O(m + n)`，最壞情況下的復雜度為`O(mn)`。 當所有窗口出現虛假命中數時，最壞情況下的復雜度就會發生。 * * * ## Rabin-Karp 算法應用 * 用于模式匹配 * 用于在較大的文本中搜索字符串