|
Boyer-Moore算法 该算法是Boyer和Moore提出了。将被搜索内容与从右到左而不是从左到右的文本进行比较，同时保持移位方向相同. [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
| public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
int i = 0, j = 0;
while ((i + patternSize) <= textSize) {
j = patternSize - 1;
while (text[i + j] == pattern[j]) {
j--;
if (j < 0)
return i;
}
i++;
}
return -1;
}
|
Boyer-Moore-Horspool算法Boyer-Moore 算法的启发式实现有许多变体，最简单的一种是 Horspool 变体。 这个版本的算法被称为Boyer-Moore-Horspool，这个变体解决了负偏移的问题（我们可以在Boyer-Moore算法的描述中读到负偏移问题）。 与 Boyer-Moore 算法一样，最坏情况的时间复杂度为 O（m * n），而平均复杂度为 O（n）。空间使用不取决于模式的大小，而只取决于字母的大小，即 256，因为这是英文字母中 ASCII 字符的最大值 [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
| public static int BoyerMooreHorspoolSearch(char[] pattern, char[] text) {
int shift[] = new int[256];
for (int k = 0; k < 256; k++) {
shift[k] = pattern.length;
}
for (int k = 0; k < pattern.length - 1; k++){
shift[pattern[k]] = pattern.length - 1 - k;
}
int i = 0, j = 0;
while ((i + pattern.length) <= text.length) {
j = pattern.length - 1;
while (text[i + j] == pattern[j]) {
j -= 1;
if (j < 0)
return i;
}
i = i + shift[text[i + pattern.length - 1]];
}
return -1;
} |
| 
发表于 2025-2-5 20:00:30