KMP模式匹配算法

参考博客 https://blog.csdn.net/wolfGuiDao/article/details/108299448

KMP代码Java版本实现

package arithmetic;

public class KMP {
  public static int[] getNext(String pattern) {
    char[] patternChar = pattern.toCharArray();
    int[] next = new int[patternChar.length + 1];
    next[0] = -1;
    int k = 0;
    int i = 2; // i表示next数组的索引
    while (i < next.length) {
      if (patternChar[i - 1] == patternChar[k]) {
        next[i] = k + 1;
        k = next[i];
        ++i;
      } else if (k == 0) {
        next[i] = 0;
        ++i;
      } else {
        k = next[k];
      }
    }
    return next;
  }

  public static int kmp(String str, String pattern) {
    int[] next = getNext(pattern);
    int i = 0;
    int j = 0;
    while (i < str.length()) {
      if (str.charAt(i) != pattern.charAt(j)) {
        j = next[j];
        if (j == -1) { // 表示当前没有匹配的字符
          i++; // 寻找下一个匹配的pattern首字母
          j = 0; // 指针移动到pattern的开头
        }
      } else {
        i++;
        j++;
        if (j == pattern.length()) {
          return (int) (i - pattern.length());
        }
      }
    }
    return -1;
  }

}