具体在class Find中的buildNext函数里
似乎是下标越界
package com.company;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String P;
String T;
while(input.hasNext())
{
P=input.next();
T=input.next();
Find op = new Find(T,P);
System.out.println(op.getCount());
}
}
}
class Find{
private int count;
private String T;
private String P;
private int[] next;
private void buildNext(){
int i=0;
int j=-1;
while(j<P.length()){
if(j==-1||P.charAt(i)==P.charAt(j)){
++i; ++j;
next[i]=j;
}else{
j=next[j];
}
}
}
public Find(String T,String P){
next=new int[P.length()];
next[0]=-1;
this.T=T; this.P=P;
count=0;
buildNext();
KMP();
}
public int getCount(){
return count;
}
private void KMP(){
int i=0,j=0;
while(i<T.length()){
if(j<0||T.charAt(i)==P.charAt(j)){
++i; ++j;
}else{
j=next[j];
}
if(j==P.length()){
++count;
j=next[j];
}
}
}
}
debug了挺久似乎看不出来哪出问题了?
我只说一点,i和j是同步增长的,j比i小1,同时条件是j<P.length()
如果还是不明白,请拿笔在纸上画一下
if(j==-1||P.charAt(i)==P.charAt(j)){ ++i; ++j; next[i]=j; }else{ j=next[j]; }
debug时重点看下这部分的逻辑,最好进去看
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。