字符串匹配算法

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算法是字符串处理惩罚中的经典算法，用来办理字符串匹配题目，明确它对提升算法操持本领照旧很有资助的。