Boyer-Moore算法

该算法是Boyer和Moore提出了。将被搜索内容与从右到左而不是从左到右的文本进行比较，同时保持移位方向相同.

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 字符的最大值

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;
}