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

KMP算法中的nextval函数值的原理！！！求详细推导！！
rt
　
再次强调，求详细推导过程，请勿灌水！

[解决办法]
原理和最后与长串匹配原理一样
都是找一个最长的与当前位置能匹配的
[解决办法]

Java code

// 这个没对模式串进行优化操作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
建议看下我的这篇文章