//Knuth, Morris, Pratt String Matching Algorithm

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int kmp(string p, string t) {
  int m=p.size(),n=t.size();
  if(n<m||m==0)return -1;
  vector<int> next(m,-1);
  int i=0,j=1;
  while(j<m) {
    if(p[i]==p[j])next[j]=next[i];
    else {
      next[j]=i;
      i=next[i];
      while(i>0&&p[i]!=p[j])i=next[i];
    }
    i++;j++;
  }
  i=0;j=0;
  while(j<n) {
    while(i>-1&&p[i]!=t[j])i=next[i];
    i++;j++;
    if(i==m)return j-i;
  }
  return -1;
}

int main() {
  cout<<kmp("this is a test","athis is a test")<<endl;
  return 0;
}