求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[ ]数组，实现串匹配，但运行出现数组越界异常，请帮忙看下正确的实现方法

展开

收起

蛮大人123 2016-06-07 14:29:11 1929 0

1 条回答

写回答

取消提交回答

蛮大人123

我说我不帅他们就打我，还说我虚伪

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

赞同展开评论打赏

问答地址：

开发者社区 > 云计算 > 问答

求nextValue数组实现串模式匹配

相关电子书