求nextValue数组实现串模式匹配
如下代码：
class KMP{
public void getNext(char T[],int nextval[]){
int i=1,j=0;
nextval[1] = 0;
while(i<T[0]){
if(j==0||T[i]==T[j]){
++i;
++j;
if(T[i]!=T[j]){ //Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException
nextval[i] = j;
}else{
j = nextval[i];
}
}else{
j = nextval[j];
}
}
}
public void kmp(char S[],char T[]){
int i=0,j=0;
int next[] = new int[80];
getNext(T,next);
for(;i<S.length&&j<T.length;){
if(S[i]==T[j]){
i++;
j++;
}else{
j = next[j];
if(j == -1){
i++;
j++;
}
}
}
if(j==T.length){
System.out.println(i-T.length+1);
}else{
System.out.println("匹配失败");
}
}
}
public class String_matching {
public static void main(String[] args) {
String str1 = "abababac";
String str2 = "bac";
char S[] = str1.toCharArray();
char T[] = str2.toCharArray();
KMP k = new KMP();
k.kmp(S, T);
}
}通过求nextValue[ ]数组，实现串匹配，但运行出现数组越界异常，请帮忙看下正确的实现方法
展开
收起
1
条回答
写回答
写回答
-
我说我不帅他们就打我，还说我虚伪public class KMPTest { public static void main(String[] args) { String s = "abbabbbbcab"; // 主串 String t = "bbcab"; // 模式串 char[] ss = s.toCharArray(); char[] tt = t.toCharArray(); System.out.println(KMP_Index(ss, tt)); // KMP匹配字符串 } /** * 获得字符串的next函数值 * * @param t * 字符串 * @return next函数值 */ public static int[] next(char[] t) { int[] next = new int[t.length]; next[0] = -1; int i = 0; int j = -1; while (i < t.length - 1) { if (j == -1 || t[i] == t[j]) { i++; j++; if (t[i] != t[j]) { next[i] = j; } else { next[i] = next[j]; } } else { j = next[j]; } } return next; } /** * KMP匹配字符串 * * @param s * 主串 * @param t * 模式串 * @return 若匹配成功，返回下标，否则返回-1 */ public static int KMP_Index(char[] s, char[] t) { int[] next = next(t); int i = 0; int j = 0; while (i <= s.length - 1 && j <= t.length - 1) { if (j == -1 || s[i] == t[j]) { i++; j++; } else { j = next[j]; } } if (j < t.length) { return -1; } else return i - t.length; // 返回模式串在主串中的头下标 } }2019-07-17 19:30:03赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
