|
在介绍Rabin Karp算法前，先看看简单文本搜索算法。 简单文本搜索遍历文本，如果模式的第一个字母匹配，则检查模式的所有字母是否都与文本匹配。
如果 m 是要搜索的字母数，n 是被搜索文本中的字母数，则该算法的时间复杂度为 O（m（n-m + 1））。 public static int simpleTextSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length; int i = 0;while ((i + patternSize) <= textSize) { int j = 0; while (text[i + j] == pattern[j]) { j += 1; if (j >= patternSize) return i; } i += 1;}return -1;}
当模式很长并且模式中有很多重复元素时，简单文本搜索算法效率非常低。、 Rabin Karp算法Rabin Karp 算法的想法是使用哈希来查找文本中的模式。在算法开始时，我们需要计算模式的哈希值，该哈希值稍后在算法中使用。这个过程叫做指纹计算。
预处理步骤的重要之处在于其时间复杂度为 O（m），通过文本迭代将需要 O（n），从而给出整个算法的时间复杂度 O（m+n）。 [color=var(--hltools-color)][size=1.15em]JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| public static int RabinKarpMethod(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
long prime = getBiggerPrime(patternSize);
long r = 1;
for (int i = 0; i < patternSize - 1; i++) {
r *= 2;
r = r % prime;
}
long[] t = new long[textSize];
t[0] = 0;
long pfinger = 0;
for (int j = 0; j < patternSize; j++) {
t[0] = (2 * t[0] + text[j]) % prime;
pfinger = (2 * pfinger + pattern[j]) % prime;
}
int i = 0;
boolean passed = false;
int diff = textSize - patternSize;
for (i = 0; i <= diff; i++) {
if (t == pfinger) {
passed = true;
for (int k = 0; k < patternSize; k++) {
if (text[i + k] != pattern[k]) {
passed = false;
break;
}
}
if (passed) {
return i;
}
}
if (i < diff) {
long value = 2 * (t - r * text) + text[i + patternSize];
t[i + 1] = ((value % prime) + prime) % prime;
}
}
return -1;
} |
| 
发表于 2025-2-5 19:56:52