为什么要对next进行改进呢?因为next存在缺陷。。。O(∩_∩)O哈哈~。。。

什么缺陷呢？

课上老师PPT中的那个例子不太好，并没有把核心体现出来，只是一部分，所以请结合课件和下面的例子仔细体会。

设 S串     abcabdabcabcd ； P串   abcabcd

好了，先求出P串的next[]，（听话，求出next[]，别看了，让你在自己电脑上把next求出来，不会的话，代码在上一篇博客（http://www.cnblogs.com/xiaoshanshan/p/4081693.html ））；

好了，估计你也没听话，算了，往下看吧。  

next[0..6] = {-1,0,0,0,1,2,3};

接下来重点来了，让我们看一下，KMP是怎么做的，（KMP叫你呢，快出来）   （渣） 。。。 O(∩_∩)O哈哈~。。。

这个过程有点长啊，请大家耐心往下看，（我打出来时间更长。。。。）

S      a(bcabdabcabcd)      ab(cabdabcabcd)     abc(abdabcabcd)    abca(bdabcabcd)    abcab(dabcabcd)   abcabd(abcabcd)

P      a(bcabcd)                  ab(cabcd)                 abc(abcd)               abca(bcd)                abcab(cd)               abcabc(d)

（我擦。。。看我next。。。next[5] == 2） 

S     abcabd(abcabcd)

P           abc(abcd) 

（KMP 你可以停了。） （渣）。。。。O(∩_∩)O哈哈~。。。

大家看到了吧。 看什么?  看上面讲的啊，不明白什么意思？那就往下看：

刚才 P[next[5]] == P[5] == ‘c‘ 对吧。好了，现在懂了吧，这次的匹配白匹配了，因为肯定是不匹配的。现在懂了吧。

纳尼？你还不懂，P[5] == P[2]对吧，P[5]都不行了，P[2]肯定不行啊。（next，去叫nextval来）

那么，让我在讲nextval之前，大家先看看nextval是怎么工作的吧。

S      a(bcabdabcabcd)      ab(cabdabcabcd)     abc(abdabcabcd)    abca(bdabcabcd)    abcab(dabcabcd)   abcabd(abcabcd)

P      a(bcabcd)                  ab(cabcd)                 abc(abcd)               abca(bcd)                abcab(cd)               abcabc(d)

（呀！！看我nextval。。。）

S      abcabd(abcabcd)

P                a(bcabcd)   （关键部分）

（纳尼？我再来一次。。。）

S     abcabda(bcabcd)      

P                 a(bcabcd)    （接下来我就不写了，最后就匹配了）

看到这里，请重点关注（关键部分），怎么样，是不是nextval比next牛逼一点（请看他们的区别）。

好了，话也不多说了，上代码。

 1 void Get_next(string P,int* nextval) { 2     int i,j; 3     nextval[i = 0] = j = -1; 4     int len = P.length(); 5     while (i < len - 1) { 6         if (j == -1 || P[i] == P[j]) { 7             i++,j++; 8             if (P[i] == P[j]) { 9                 nextval[i] = nextval[j];10             }11             else nextval[i] = j;12         }13         else j = nextval[j];14     }15 }

看到不同了吧，就是这么简单。

练习一下，P串 abcabcd 的nextval是多少？

nextval [0..7] = {-1,0,0,-1,0,0,3};

KMP改进（nextval）