KMP.cpp

int KMP(Str str, Str substr, int next[]){
  int i=0,j=0;
  while(i<str.length && j<substr.length){
    if(j==-1||str.ch[i] == substr.ch[j]){
      ++i;
      ++j;
    }
    else{
      j=next[j];
    }
  }
  if(j==substr.length){
    return i-substr.length;
  }
  else return -1;
}

void getnext(Str substr, int next[]){
  int i=0,j=-1;
  next[0]=-1;
  while(i<substr.length-1){
    if(substr.ch[i]==substr.ch[j]){
      ++i;
      ++j;
      next[i] = j;
    }
    else{
      j=next[j];
    }
  }
}