KMP演算法

KMP演算法是字元串模式匹配當中最經典的演算法，原來大二學數據結構的有講，但是當時只是記住了原理，但不知道代碼實現，今天終於是完成了KMP的代碼實現。
原理
KMP的原理其實很簡單，給定一個字元串和一個模式串，然後找模式串在給定字元串中的位置。將兩個字元串轉換為字元數組，然後從兩個數組的開始位置"i"，"j"開始匹配，如果相同，執行"i++"，"j++"接著比較下一位；如果不相同，就轉到模式串對應next數組的對應位置"next[j]"然後從該位置開始繼續與給定字元串的當前位置"i"進行比較，換句話說就是將模式串提前了"j-next[j]"位繼續比較，不至於每次出現不匹配就又重新回到開始位置進行匹配，充分利用了已匹配過的位置。

代碼
KMP演算法的關鍵是得到模式串的next數組：

public static int[] next(char[] p) {
  int len = p.length;
  int[] next = new int[len];
  next[0] = 0;
  next[1] = 0; //首先給next[0]和next[1]賦值，這兩個數字是固定的
  for(int i = 2; i < len; i++) {
    int k = next[i - 1]; //用一個整型數字進行遍歷
    while(k >= 0) {
      if(p[i - 1] == p[k]) {
        next[i] = k + 1; //當匹配到字元時就能得到當前位置的next值，然後結束迴圈
        break;
      }
      k--;
    }
  }
  return next;
}        

得到next數組之後就可以進行KMP匹配：

public int kmpSearch(char[] s, char[] p) {
  int i = 0, j = 0; //從0開始
  int slen = s.length, plen = p.length;
  int[] next = next(p);
  while(i < slen && j < plen) {
    if(s[i] == p[j]) { //挨個進行匹配
      i++;
      j++;
    } else {
      j = next[j]; //如果不相等，返回next[j]位置繼續向後匹配，不用和前面的進行比較
    }
  }
  if(j == plen) //如果匹配到最後，說明匹配成功，返回匹配成功的開始位置
    return i - j;
  return -1; //否則就是匹配失敗，返回-1
}

KMP演算法還有一個進階的next演算法，求nextval數組：

public int[] nextVal(char[] p) {
  int len = p.length;
  int[] nextval = new int[len];
  nextval[0] = -1;
  int i=-1, j = 0;
  while(j < len - 1) {
  if(i == -1 || p[j] == p[i]) {
    ++i;
    ++j;
    if(p[j] != p[i])
      nextval[j] = i;
    else
      nextval[j] = nextval[i];
  }else 
      i = nextval[i];
  }
  return nextval;
}