字符串匹配算法

Rabin-Karp算法

Rabin-Karp算法是一种基于哈希函数的字符串匹配算法，由 Michael O. Rabin 和 Richard M. Karp 于1987年提出，核心思想是用哈希函数将模式串和文本串中的子串转换为数值进行比较，避免大量不必要的字符比较。这个算法特别适合多模式串匹配场景，时间复杂度平均为O(n+m)，n是文本串长度，m是模式串长度。
Rabin-Karp算法的关键在于使用滚动哈希函数（Rolling Hash），它可以在常数时间内计算出滑动窗口的新哈希值，保证算法在大多数情况下的高效性。
算法步骤

• 计算模式串的哈希值
  
• 计算文本串中长度为m的第一个子串的哈希值（m为模式串长度）
  
• 在文本串上滑动窗口，对于每个位置：
  
  
  
  • 使用滚动哈希技术高效计算当前窗口的哈希值
    
  • 如果哈希值与模式串相等，则进行字符逐一比较以避免哈希冲突
    
  • 如果完全匹配，则找到一个匹配位置
    
  
  
• 重复步骤3，直到处理完整个文本串
  

核心特性

• 基于哈希比较：通过哈希值比较代替直接字符比较
  
• 滚动哈希：O(1)时间复杂度计算下一窗口的哈希值
  
• 时间复杂度：平均情况O(n+m)，最坏情况O(n*m)
  
• 空间复杂度：O(1)，只需常数额外空间
  
• 适用范围：单模式和多模式串匹配场景，特别是多模式匹配
  

基础实现

接下来大家一起看下Rabin-Karp算法的部分主流语言实现：

1. public class RabinKarp {
2.     private final static int PRIME = 101; // 哈希计算使用的质数
3.    
4.     public static int search(String text, String pattern) {
5.         int m = pattern.length();
6.         int n = text.length();
7.         
8.         if (m > n) return -1;
9.         if (m == 0) return 0;
10.         
11.         // 计算哈希乘数，等于d^(m-1) % PRIME，用于滚动哈希计算
12.         int h = 1;
13.         for (int i = 0; i < m - 1; i++) {
14.             h = (h * 256) % PRIME;
15.         }
16.         
17.         // 计算模式串和第一个窗口的哈希值
18.         int patternHash = 0;
19.         int textHash = 0;
20.         for (int i = 0; i < m; i++) {
21.             patternHash = (256 * patternHash + pattern.charAt(i)) % PRIME;
22.             textHash = (256 * textHash + text.charAt(i)) % PRIME;
23.         }
24.         
25.         // 滑动窗口，比较哈希值
26.         for (int i = 0; i <= n - m; i++) {
27.             // 哈希值相等时，检查是否真正匹配
28.             if (patternHash == textHash) {
29.                 boolean match = true;
30.                 for (int j = 0; j < m; j++) {
31.                     if (text.charAt(i + j) != pattern.charAt(j)) {
32.                         match = false;
33.                         break;
34.                     }
35.                 }
36.                 if (match) {
37.                     return i; // 找到匹配
38.                 }
39.             }
40.             
41.             // 计算下一个窗口的哈希值
42.             if (i < n - m) {
43.                 textHash = (256 * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % PRIME;
44.                 // 处理负数哈希值
45.                 if (textHash < 0) {
46.                     textHash += PRIME;
47.                 }
48.             }
49.         }
50.         
51.         return -1; // 未找到匹配
52.     }
53.    
54.     // 打印结果
55.     public static void main(String[] args) {
56.         String text = "ABABCABABDABACDABABCABAB";
57.         String pattern = "ABABCABAB";
58.         
59.         int position = search(text, pattern);
60.         if (position == -1) {
61.             System.out.println("未找到匹配");
62.         } else {
63.             System.out.println("模式串在位置 " + position + " 处匹配");
64.             System.out.println(text);
65.             // 打印指示匹配位置的指针
66.             for (int i = 0; i < position; i++) {
67.                 System.out.print(" ");
68.             }
69.             System.out.println(pattern);
70.         }
71.     }
72. }

复制代码

在上述代码中：

1. public class ImprovedRabinKarp {
2.     private final static long PRIME1 = 1000000007; // 第一个哈希的质数
3.     private final static long PRIME2 = 1000000009; // 第二个哈希的质数
4.    
5.     // 使用双哈希来减少冲突
6.     public static int search(String text, String pattern) {
7.         int m = pattern.length();
8.         int n = text.length();
9.         
10.         if (m > n) return -1;
11.         if (m == 0) return 0;
12.         
13.         // 计算哈希乘数
14.         long h1 = 1;
15.         long h2 = 1;
16.         for (int i = 0; i < m - 1; i++) {
17.             h1 = (h1 * 256) % PRIME1;
18.             h2 = (h2 * 256) % PRIME2;
19.         }
20.         
21.         // 计算模式串和第一个窗口的哈希值
22.         long patternHash1 = 0;
23.         long patternHash2 = 0;
24.         long textHash1 = 0;
25.         long textHash2 = 0;
26.         
27.         for (int i = 0; i < m; i++) {
28.             patternHash1 = (256 * patternHash1 + pattern.charAt(i)) % PRIME1;
29.             patternHash2 = (256 * patternHash2 + pattern.charAt(i)) % PRIME2;
30.             textHash1 = (256 * textHash1 + text.charAt(i)) % PRIME1;
31.             textHash2 = (256 * textHash2 + text.charAt(i)) % PRIME2;
32.         }
33.         
34.         // 滑动窗口，比较哈希值
35.         for (int i = 0; i <= n - m; i++) {
36.             // 两个哈希都相等时，再进行字符比较
37.             if (patternHash1 == textHash1 && patternHash2 == textHash2) {
38.                 boolean match = true;
39.                 for (int j = 0; j < m; j++) {
40.                     if (text.charAt(i + j) != pattern.charAt(j)) {
41.                         match = false;
42.                         break;
43.                     }
44.                 }
45.                 if (match) {
46.                     return i; // 找到匹配
47.                 }
48.             }
49.             
50.             // 计算下一个窗口的哈希值
51.             if (i < n - m) {
52.                 textHash1 = (256 * (textHash1 - text.charAt(i) * h1) + text.charAt(i + m)) % PRIME1;
53.                 textHash2 = (256 * (textHash2 - text.charAt(i) * h2) + text.charAt(i + m)) % PRIME2;
54.                
55.                 // 处理负数哈希值
56.                 if (textHash1 < 0) textHash1 += PRIME1;
57.                 if (textHash2 < 0) textHash2 += PRIME2;
58.             }
59.         }
60.         
61.         return -1; // 未找到匹配
62.     }
63. }

复制代码

是 KMP 算法的核心，在匹配失败时根据预先计算的next数组来确定模式串指针的回退位置。
优化

优化后的 next 数组

1. public class RabinKarpFingerprint {
2.     private final static long PRIME = 1000000007;
3.     private final static int WINDOW_SIZE = 5; // 指纹窗口大小
4.    
5.     public static Set<Long> generateFingerprints(String text) {
6.         Set<Long> fingerprints = new HashSet<>();
7.         int n = text.length();
8.         
9.         if (n < WINDOW_SIZE) {
10.             fingerprints.add(calculateHash(text, n));
11.             return fingerprints;
12.         }
13.         
14.         // 计算第一个窗口的哈希值
15.         long textHash = calculateHash(text, WINDOW_SIZE);
16.         fingerprints.add(textHash);
17.         
18.         // 计算哈希乘数
19.         long h = 1;
20.         for (int i = 0; i < WINDOW_SIZE - 1; i++) {
21.             h = (h * 256) % PRIME;
22.         }
23.         
24.         // 滑动窗口，计算所有长度为WINDOW_SIZE的子串哈希值
25.         for (int i = 0; i <= n - WINDOW_SIZE - 1; i++) {
26.             textHash = (256 * (textHash - text.charAt(i) * h) + text.charAt(i + WINDOW_SIZE)) % PRIME;
27.             if (textHash < 0) {
28.                 textHash += PRIME;
29.             }
30.             fingerprints.add(textHash);
31.         }
32.         
33.         return fingerprints;
34.     }
35.    
36.     public static double calculateSimilarity(String text1, String text2) {
37.         Set<Long> fingerprints1 = generateFingerprints(text1);
38.         Set<Long> fingerprints2 = generateFingerprints(text2);
39.         
40.         // 计算交集大小
41.         Set<Long> intersection = new HashSet<>(fingerprints1);
42.         intersection.retainAll(fingerprints2);
43.         
44.         // 计算并集大小
45.         Set<Long> union = new HashSet<>(fingerprints1);
46.         union.addAll(fingerprints2);
47.         
48.         // 杰卡德相似度系数
49.         return (double) intersection.size() / union.size();
50.     }
51.    
52.     private static long calculateHash(String str, int length) {
53.         long hash = 0;
54.         for (int i = 0; i < length; i++) {
55.             hash = (256 * hash + str.charAt(i)) % PRIME;
56.         }
57.         return hash;
58.     }
59. }

复制代码

预处理减少分支实现

1. public class SubstringHash {
2.     private static final long PRIME = 1000000007;
3.     private static final int BASE = 256;
4.    
5.     private long[] hash; // 前缀哈希值
6.     private long[] pow;  // BASE的幂
7.     private String s;    // 源字符串
8.    
9.     public SubstringHash(String s) {
10.         this.s = s;
11.         int n = s.length();
12.         hash = new long[n + 1];
13.         pow = new long[n + 1];
14.         
15.         // 预计算BASE的幂
16.         pow[0] = 1;
17.         for (int i = 1; i <= n; i++) {
18.             pow[i] = (pow[i - 1] * BASE) % PRIME;
19.         }
20.         
21.         // 计算所有前缀的哈希值
22.         hash[0] = 0;
23.         for (int i = 0; i < n; i++) {
24.             hash[i + 1] = (hash[i] * BASE + s.charAt(i)) % PRIME;
25.         }
26.     }
27.    
28.     // 计算子串s[l..r]的哈希值（0-indexed）
29.     public long substringHash(int l, int r) {
30.         // 获取s[0...r]的哈希值，减去s[0...l-1]的哈希值（需要进行适当调整）
31.         long result = (hash[r + 1] - (hash[l] * pow[r - l + 1]) % PRIME) % PRIME;
32.         if (result < 0) {
33.             result += PRIME;
34.         }
35.         return result;
36.     }
37.    
38.     // 检查两个子串是否相同
39.     public boolean areSubstringsEqual(int l1, int r1, int l2, int r2) {
40.         if (r1 - l1 != r2 - l2) {
41.             return false; // 长度不同
42.         }
43.         return substringHash(l1, r1) == substringHash(l2, r2);
44.     }
45. }

复制代码

优点

• 时间复杂度为O(m+n)，优于朴素的字符串匹配算法(暴力解法)
  
• 文本串只需扫描一次，不会回退
  
• 对于包含重复模式的字符串会高效
  
• 预处理模式串，可以多次用于不同的文本串
  
• 能快速跳过已知不会匹配的位置
  

缺点

• 需要额外的空间存储next数组
  
• 构建next数组的逻辑较为复杂，不易理解
  
• 在模式串较短或无重复模式时，相比简单算法优势不明显
  
• 实现时容易出错，特别是处理边界情况
  

应用场景

1）生物信息学中的DNA序列匹配
2）网络入侵检测系统中的模式匹配
3）搜索引擎的关键词匹配
4）数据压缩算法中的模式识别
扩展：多模式字符串匹配

1. public class BoyerMoore {
2.     private final int R; // 字符集大小
3.     private int[] badChar; // 坏字符表
4.     private int[] goodSuffix; // 好后缀表
5.     private int[] borderPos; // 边界位置表
6.     private String pattern; // 模式串
7.    
8.     public BoyerMoore(String pattern) {
9.         this.R = 256; // ASCII字符集
10.         this.pattern = pattern;
11.         int m = pattern.length();
12.         
13.         // 初始化坏字符表
14.         badChar = new int[R];
15.         for (int c = 0; c < R; c++) {
16.             badChar[c] = -1; // 初始化为-1
17.         }
18.         for (int j = 0; j < m; j++) {
19.             badChar[pattern.charAt(j)] = j; // 记录每个字符最右出现位置
20.         }
21.         
22.         // 初始化好后缀表和边界位置表
23.         goodSuffix = new int[m];
24.         borderPos = new int[m];
25.         processSuffixes();
26.     }
27.    
28.     // 预处理好后缀表
29.     private void processSuffixes() {
30.         int m = pattern.length();
31.         int i = m, j = m + 1;
32.         borderPos[i] = j;
33.         
34.         // 计算边界位置
35.         while (i > 0) {
36.             while (j <= m && pattern.charAt(i - 1) != pattern.charAt(j - 1)) {
37.                 if (goodSuffix[j] == 0) {
38.                     goodSuffix[j] = j - i;
39.                 }
40.                 j = borderPos[j];
41.             }
42.             i--; j--;
43.             borderPos[i] = j;
44.         }
45.         
46.         // 计算好后缀表
47.         j = borderPos[0];
48.         for (i = 0; i <= m; i++) {
49.             if (goodSuffix[i] == 0) {
50.                 goodSuffix[i] = j;
51.             }
52.             if (i == j) {
53.                 j = borderPos[j];
54.             }
55.         }
56.     }
57.    
58.     // 搜索文本串中的匹配
59.     public int search(String text) {
60.         int n = text.length();
61.         int m = pattern.length();
62.         if (m == 0) return 0;
63.         
64.         int skip;
65.         for (int i = 0; i <= n - m; i += skip) {
66.             skip = 0;
67.             for (int j = m - 1; j >= 0; j--) {
68.                 if (pattern.charAt(j) != text.charAt(i + j)) {
69.                     // 坏字符规则
70.                     skip = Math.max(1, j - badChar[text.charAt(i + j)]);
71.                     // 好后缀规则
72.                     if (j < m - 1) {
73.                         skip = Math.max(skip, goodSuffix[j + 1]);
74.                     }
75.                     break;
76.                 }
77.             }
78.             if (skip == 0) return i; // 找到匹配
79.         }
80.         return -1; // 没有找到匹配
81.     }
82.    
83.     // 测试
84.     public static void main(String[] args) {
85.         String text = "HERE IS A SIMPLE EXAMPLE";
86.         String pattern = "EXAMPLE";
87.         
88.         BoyerMoore bm = new BoyerMoore(pattern);
89.         int position = bm.search(text);
90.         
91.         if (position == -1) {
92.             System.out.println("未找到匹配");
93.         } else {
94.             System.out.println("模式串在位置 " + position + " 处匹配");
95.             System.out.println(text);
96.             for (int i = 0; i < position; i++) {
97.                 System.out.print(" ");
98.             }
99.             System.out.println(pattern);
100.         }
101.     }
102. }

复制代码

相关的 LeetCode 热门题目

• 28. 找出字符串中第一个匹配项的下标 - 标准的字符串匹配问题
  
• 214. 最短回文串 - 可以使用KMP算法的next数组思想解决
  
• 459. 重复的子字符串 - 使用KMP的next数组判断字符串是否由重复子串构成
  
• 1392. 最长快乐前缀
  

KMP算法是字符串处理中的经典算法，用来解决字符串匹配问题，理解它对提升算法设计能力还是很有帮助的。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！