notebook/code/kmp.cpp

// Given a string S of length n, the KMP algorithm produces an array pnext
// where pnext[i+1] is the length of the longest substring ending at S[i] which is also a prefix of S
void kmp_pre(char x[], int m, int pnext[]) {
  int i,j;
  j=pnext[0]=-1;
  i=0;
  while (i<m) {
    while (-1!=j && x[i]!=x[j]) j=pnext[j];
    pnext[++i]=++j;
  }
}
// x pattern, y text
// answer: first index (starting with 0)
// KMP_Count : # occurences
int pnext[100005];
int KMP(char x[], int m, char y[], int n) { // KMP_Count
  int i,j; // int ans = 0;
  kmp_pre(x,m,pnext);
  i=j=0;
  while(i<n) {
    while(-1!=j && y[i]!=x[j]) j=pnext[j];
    i++; j++;
    if (j>=m) {
      return i-m; // ans++; j=pnext[j];
    }
  }
  return -1; // return ans;
}