2 steve yanrun steve_yanrun 于 2016.03.24 11:40 提问

求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个回答

wojiushiwo945you
wojiushiwo945you   Ds   Rxr 2016.03.24 14:49
已采纳

你的getNext算法实现有问题,你的while(i<T[0])但实际上你的T[0]并不是存储的数组的长度的。
给个正确版本的实现:http://blog.csdn.net/tkd03072010/article/details/6824326

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!