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));
}
}
public void getnext(char s[],int next[])
应该是
public void getnext(char[] s,int[] next)
吧,你用的看上去是Java,可是怎么混杂着C++的语法。
另外你可以google java kmp算法找一个现成的程序参考下,看得出你连基本语法都还不会。
while(s[j]!='\0'),你这条件会为false吗?死循环,导致j数组越界。
这写法有点C语言的风格。
数组 t 和 s 的数据都没有字符串结束符的,所以用 == 0 作为判断是错误的。如果将等于的判断写成赋值,就更加的错误了!
如果你的代码就是这么一点的话,你的j没变,如果s[j]是不等于\0,那么就是一个死循环
不好意思,看错了
如果不满足条件应该是数组过界
next 容易 混淆,换个大写的My_next 如何