public class next {
public void getnext(char s[],int next[])
{
int j=0;
int k=-1;
next[0]=-1;
while(s[j]!='\0')
{
if(k==-1)
{
next[++j]=0;
k=0;
}
else if(s[j]==s[k])
{
k++;
next[++j]=k;
}
else
{
k=next[k];
}
}
}
}
public class kmp {
public int kmp(char t[],char s[])
{
int i=0,j=0;
int []nex=new int[80];
next n=new next();
n.getnext(s,nex);
while(t[i]!='\0'&&s[j]!='\0')
{
if(t[i]==s[j])
{
i++;
j++;
}
else
{
j=nex[j];
if(j==-1)
{
i++;
j++;
}
}
}
if(s[j]=='\0')
{
return(i-s.length+1);
}
else
{
return 0;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
char []t={'q','w','e','r','s','a','a'};
char []s={'s','a'};
kmp k=new kmp();
System.out.print(k.kmp(t, s));
}
}