#include <iostream>
#include <stdio.h>
using namespace std;
#define m 100
#define n 100
void GetNext(char *t,int *next);
int KMP(char *s,char *t,int pos,int *next);
void main()
{
int k;
char s[m];
char t[n];
cout<<"input s"<<endl;
cin>>s;
cout<<"input t"<<endl;
cin>>t;
int next[n];
GetNext(t,next);
k=KMP(s,t,1,next);
cout<<k;
getchar();
}
void GetNext(char *t,int *next)
{
int i,j,k=1,len;
len=strlen(t);
for(i=0;i<len;i++)
next[i]=1;
for(i=1;i<len;i++)
{
j=i;
while(t[j]==t[k]&&j<len)
{
k++;j++;
}
if(next[j]<k)
next[j]=k;
k=1;
}
}
int KMP(char *s,char *t,int pos,int *next)
{
int i=0,j=0,len1,len2;
len1=strlen(s);
len2=strlen(t);
while(i<len1&&j<len2)
{
if(s[i]==t[j])
{i++;j++;}
else
{
if(j>1)
j=next[j];
else
i++;
}
if(j==len2)
return i-j+1;
}
return -1;
}
