求nextValue数组实现串模式匹配

Question

如下代码：

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

Answer 1

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