#include <iostream>

#include <iomanip>

using namespace std;

void preKmp(char* s,int len,int* next)

{

    int i=,j=-;

    next[]=-;

    while(i<len)

    {

        while(j>- && s[i]!=s[j])

            j=next[j];

        i++;

        j++;

        if(s[i]==s[j])

            next[i]=next[j];

        else

            next[i]=j;

    }

}

int KMP(char*s,char* p)

{

    int sn=strlen(s);

    int sp=strlen(p);

    int* next=new int[sp];

    preKmp(p,sp,next);

    int i=,j=;

    while(i<sn)

    {

        while(j>- && s[i]!=p[j])

            j=next[j];

        i++;

        j++;

        if(j>=sp)

        {

            return i-j;

        }

    }

    return -;

}

int main(int argc, char* argv[])

{

    char* p="abcdabceabcde";

    char* s="abcdabcdabceabcde";

    int pos=KMP(s,p);

    cout<<pos<<endl;

    return ;

}