Knuth-Morris-Pratt算法

admin

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

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

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