#include <vector>
#include <string>
using namespace std;
const vector<int> * kmp_next(string &m) // count the longest prefex string ;
{
static vector<int> next(m.size());
next[0]=0; // the initialization of the next[0];
int temp; // the key iterator......
size_t nSz = next.size(), i;
for(i = 1; i < nSz; i++)
{
temp=next[i-1];
while(m[i] != m[temp] && temp>0)
{
temp=next[temp-1];
}
if(m[i] == m[temp])
next[i] = temp + 1;
else next[i] = 0;
}
return &next;
}
bool kmp_search(string text,string m,int &pos)
{
const vector<int> * next = kmp_next(m);
int tp = 0;
int mp = 0; // text pointer and match string pointer;
int nSz = (int)text.size();
for(tp = 0;tp < nSz; tp++)
{
while(text[tp] != m[mp] && mp)
mp = (*next)[mp-1];
if(text[tp] == m[mp])
mp++;
if(mp == m.size())
{
pos = tp - mp + 1;
return true;
}
}
if(tp == text.size())
return false;
}
