Question

关于KMP算法求next值的问题

严的数据结构第83页关于KMP算法模式串next值，原文如下：

若Pk=Pj，则表明在模式串中 'P1....Pk' = 'Pj-k+1.....Pj'
并且不可能存在k‘>k满足以上等式，也就是说 next[j+1]=k+1
即：
next[j+1]=next[j]+1

请问这个 next[j+1]=k+1是怎么得来的？这里纠结了好久都看不懂，还有那个 k‘是什么

Answer 1

额这个问题之前没多久给别人解答过，我就直接搬过来了……
————————————————————————————————————————
好吧~KMP当初我也想了挺久的~很巧妙的算法啊！相必复制百科什么的你也不会看的了所以我手打吧…下面是我的理解~
为了解说方便我把长的称为文本串，短的称为目标串~
常规的匹配算法是把目标串一位一位地右移，跟文本串比较，而KMP则是跳着右移~
举几个例子相信你就懂了
————————————————————————————————————————
比如有一目标串为ababaca，当前位置匹配了前5个，也就是匹配了ababa，后面两个不匹配
这说明了文本串当前位置也是ababa
显然右移一位是不行的，因为从目标串可以看出(abab)a与a(baba)括号里的内容不相等
而右移两位是可能可行的~因为可以看出(aba)ba与ab(aba)括号里的内容是相等的，这意味着移动两位后，目标串前三位aba是肯定匹配的~因为移动前也匹配~
————————————————————————————————————————
再举一个例子~比如有目标串abcab，当前位置匹配了前两个ab
那么就需要右移3个位置，因为(ab)cab与abc(ab)括号里内容相同，移动后有可能会匹配~
————————————————————————————————————————
懂了么？表达能力有限…我也不能讲得更好了…具体代码网上一大堆，《算法导论》里面也有~我当初就是在算导里学会的！
如果懂了，希望有追加分啊，手打累死！！！
不懂的话，追问吧……

追问

你说的这些我都懂了，只是上面说的那个式子那里不开窍，能解释一下吗？

追答

我学的书是算法导论啊……想问下你那个next是记录什么的？有两种记录的方法的……

Answer 2

唉，这题说实话确实搞哭了一代人，这里有我以前回答过的关于KMP的问题，看看有木有帮助吧。
http://zhidao.baidu.com/question/539900670?&oldq=1

追问

能简单解释一下 next[j+1]=k+1 这个式子是怎么推导出来的吗？ 后面那个怎么算模式串的例子可以看懂，就是（abaabc -》011223）这个，只是上面这个式子实在不知道是怎么搞出来的

追答

严版P83——（4-11）
这部分还是求Next值的啊。
数组Next中是回朔值，这个你好像已经知道了。
那么，当任意一个模式串被用来算next值的时候：
1.next[1]=0 4-6
2.注意， 设next[j]=k 此处 查看4-2部分：'p1p2...pk-1'='si-k+1...si-1'
再看看4-3部分，可推出4-4：'p1 p2...pk-1'='pj-k+1 pj-k+2..pj-1‘
3.这里next是存放回朔值的！由2.可知4-10是成立的。
'p1...pk'='pj-k+1...pi‘ (4-10)

4.好了，之前你都没问题的，对吧。
到了这里已经明明白白说了
next[j+1]=k'+1 → next[j+1]=next[k]+1
即：回朔值可以再往前推一个位置！

我强烈建议你明天早上别背英语了，早起把这部分读两遍，直接解决问题，真心的！

追问

就是说
Pj-k+1...Pi (模式串)
P1.........Pk (模式串每个元素对应的回溯值指向的元素）
这两列相等了的话，Pi回溯时回到Pk，Pj-k+1回溯时回到P1，那么往后推可得Pi+1回溯时回到Pk+1，是这样吗？

追答

p1....pk
pj-k+1...pi都是模式串；
这里的问题是不匹配则向右滑动，滑动多少才是主要问题。
因此，匹配的时候前边若是匹配，则后边对应有一个相等的序列。这两个式子指的是这个意思。
后边你说对了...