void Getnext(int next[],char *MyString)

{

   int j=,k=-;

   next[]=-;//规定，方便后面k的计算

   while(j<strlen(MyString)-)//j不能超过整个串的长度

   {

      //j为当前字符,k为j前面那些字符的最长公共前后缀的下一个字符

      if(k == - || MyString[j] == MyString[k])next[++j] = ++k;

      //模式串的第一个字符就要比较的字符不一样,那我就要将模式串的下一个字符和我要比较的字符比较，且现在k还是为-1的，所以++j,++k

      else k = next[k];

   }

}

int Kmp(char *T,int numt,char *P,int nump,int *next)//T为主串，P为模式串

{

    int i=,j=;//i为主串的指针，j为模式串的指针

    while(i<=numt-nump)

    {

        while((T[i]==P[j]&&i<numt)||j==-) ++i,++j;//j==-1

//模式串第一个就和主串中要匹配的字符不匹配，主串字符后移一位，模式串的指针也从-1恢复到零

        if(j==nump)//找到匹配串

        return i-nump;//返回在主串中的起始位置

        j=next[j];

    }

    return -;//表示无法找到

}

#include <stdio.h>

#include <string.h>

void Getnext(int next[],char *MyString);

int Kmp(char *T,int numt,char *P,int nump,int *next);

const int SIZE=;

int main()

{

    char *T=new char[SIZE];

    char *P=new char [SIZE];

    int *next=new int [SIZE];

    scanf("%s",T);

    scanf("%s",P);

    Getnext(next,P);

    for(int i=;i<strlen(P);i++) printf("%d,",next[i]);

    printf("\n%d",Kmp(T,strlen(T),P,strlen(P),next));

    return ;

}

void Getnext(int next[],char *MyString)

{

   int j=,k=-;

   next[]=-;

   while(j<strlen(MyString)-)

   {

      if(k == - || MyString[j] == MyString[k])next[++j] = ++k;

      else k = next[k];

   }

}

int Kmp(char *T,int numt,char *P,int nump,int *next)//T为主串，P为模式串

{

    int i=,j=;//i为主串的指针，j为模式串的指针

    while(i<=numt-nump)

    {

        while((T[i]==P[j]&&i<numt)||j==-) ++i,++j;

        if(j==nump)//找到匹配串

        return i-nump;//返回在主串中的起始位置

        j=next[j];

    }

    return -;//表示无法找到

}