kmp算法代码及next数组思考

最难理解的部分是next数组的求解方法,自己思考了两周总是想,k失效以后,k的下一次迭代为什么会是next[k]而不是k-1。经过和牛人沟通,及看了这篇文章KMP 算法详细解析,终于想通:所有迭代过程中,最长公共前后缀的结束部分应该是含有共同的尾巴。

代码是非常简单的

  public int indexOf(String S, String P) {
    int[] nextTab = extractNext(P);
    int i = 0, j = 0, s_size = S.length(), p_size = P.length();
    while (i <= s_size - 1) {
      if (S.charAt(i) == P.charAt(j)) {
        if (j == p_size - 1) {
          return i - j;
        }
        j++;
        i++;
      } else {
        if (0 == j) {
          i++;
          continue;
        }
        j = nextTab[j];
      }
    }
    return -1;
  }

  int[] extractNext(String P) {
    final int[] nextTab = new int[P.length()];
    nextTab[0] = -1;
    int k = 0;
    for (int i = 1; i < nextTab.length; i++) {
      k = nextTab[i - 1];
      if (-1 == k || P.charAt(i - 1) == P.charAt(k)) {
        nextTab[i] = k + 1;
      } else {
        while (k != 0) {
          k = nextTab[k];
          if (P.charAt(i - 1) == P.charAt(k)) {
            nextTab[i] = k + 1;
            break;
          }
        }
        ;
      }
    }
    return nextTab;
  }