Knuth-Morris-Pratt算法也就是大家常听到的KMP算法。

如果直接比较文本，如果很多部分与被查部分匹配，算法可能会很慢。KMP采用移位表改进了这种情况。
Knuth-Morris-Pratt 算法的思想是移位表的计算，它为我们提供了应该在其中搜索候选模式的信息.
该算法的时间复杂度为O（m+n）

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
public static int KnuthMorrisPrattSearch(char[] pattern, char[] text) {
    int patternSize = pattern.length;
    int textSize = text.length;

    int i = 0, j = 0;

    int[] shift = KnuthMorrisPrattShift(pattern);

    while ((i + patternSize) <= textSize) {
        while (text[i + j] == pattern[j]) {
            j += 1;
            if (j >= patternSize)
                return i;
        }

        if (j > 0) {
            i += shift[j - 1];
            j = Math.max(j - shift[j - 1], 0);
        } else {
            i++;
            j = 0;
        }
    }
    return -1;
}