KMP algorithm C++ code

写个代码在这里吧,based on wiki。
从字符串S中找字符串W。
主要思路是：S开始match的位置sb和已经match的位数w，如果匹配就w++,如果不匹配，sb移动到next(sb) = sb + w - T[w], 此时前T[w]位已经匹配了，因此从w = T[w]位开始考察匹配。

//set up help array to find next j, assume that W.length() >=2. T[i] = the max length of equal pre-/suf- substring from W[0]->W[i-1](the first i digits).

void prefun(string W, int &T[]){
  T[0] = -1; T[1] = 0;
  int ind = 0, i = 2;
  while( i < W.length()){
     if(W[i-1] == W[ind]) {
           T[i] = ind + 1; ind++; i++;
     }
    else if(ind > 0) ind  = T[ind];
    else {T[i] = 0; i++;}
  }
  
}

//KMP search algorithm, I will write only the case W.length()>1.

int kmp_search(string S, string W) {
 int[] T = new int[W.length()];
 int sb = 0, w = 0;  //sb is the begining of match in S, w is the cur matching pos of w.
while(sb + w < S.length() ){
  if(S[sb+w] == W[w])  {
      if(w == W.length() - 1) return sb;
      else w++;
  }
 else {
   sb = sb + w  - T[w];
   if(T[w] == -1) w = 0;
   else w = T[w];
  }
}
}
 return S.length();
}