KMP.cpp

int KMP(string T,string p){
  int n=p.length();
  int N=T.length();
  int *A=new int[n];
  longestPrefixSuffix(p,A,n);   // compute lps array
  int i=0,j=0;
  while(i<N){
    if(j==n){   // pattern found
      delete []A;
      return i-n;
    }
    if(T[i]==p[j]){
      i++;
      j++;
    }else if(j==0) i++;
    else j=A[j-1];
  }
  delete []A; // delete A to avoid memory leak
  if(j==n)
    return i-n;
  return -1;    // if not found return -1
}