求nextValue数组实现串模式匹配-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

求nextValue数组实现串模式匹配

2016-06-07 14:29:11 1502 1

如下代码:

 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)
  • 蛮大人123
    2019-07-17 19:30:03
    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; // 返回模式串在主串中的头下标
        }
    }
    0 0
+关注
蛮大人123
我说我不帅他们就打我,还说我虚伪
0
文章
7733
问答
问答排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载