KMP算法中的nextval函数值的原理！求详细推导！该怎么解决

// 这个没对模式串进行优化操作
char[] tar = tarStr.toCharArray();
        char[] mat = matStr.toCharArray();
        int[] nextval= new int[matStr.length()];
        nextval[0] = -1; 
        int i = 0;
        int j = -1;
        while (i < nextval.length - 1) {
            if (j == -1 || mat[i] == mat[j]) { 
                nextval[++i] = ++j;
            } else {
                j = nextval[j];
            }
        }

------解决方案--------------------
首先需要了解有穷自动机，形式语言或者编译原理里有讲
next数组存储的是一个失败函数，也就是自动机遇到没匹配上的字符时要跳回的状态，
例如 0a1b2a3b4a5a6,其中字符代表要匹配的输入，数字代表状态
于是有失败函数,此函数满足一个映射，就是next数组，这个串的失败函数是
s 1 2 3 4 5 6
f 0 0 1 2 3 1
失败函数中数字代表的状态是上面串的最长真后缀，例如
s=3时串为aba，f=1串为a，于是a是aba的最长真后缀。
失败函数的作用，当s=3时输入的字符没匹配上,那么自动机就会从3状态跳回1状态，
因为1对应的串是3的最长真后缀，直到3之前都被匹配上了，那么3的最长真后缀也就被匹配上了，
即直到1被匹配上了，所以这样就避免了重复的匹配。
举例，判断上面的字符串是否是abababaab的字串，
首先ababa都被匹配，到下一个a时没匹配上于是跳到f(5)=3,跳到3，即aba是ababa的最长真后缀，
所以aba肯定会被匹配（因为ababa能被匹配），然后baab也被匹配，就是这个过程，
大体就是这个意思，详细的最好还是看看书

------解决方案--------------------
http://www.cppblog.com/oosky/archive/2006/07/06/9486.html
去这里看，很详细的！

------解决方案--------------------
有限自动机

------解决方案--------------------
就是把模式串中的每次对比都保存下来，节省时间

------解决方案--------------------
http://blog.csdn.net/yaoweijq/archive/2010/11/02/5982508.aspx
建议看下我的这篇文章