你有KMP的代码吗 传上来啊 我书上的都是模板的伪代码 看的我发晕，发几个上来啊

斑竹你好
我现在手上的是本 清华大学的数据结构（C++版）的是殷人昆编的以我目前的情况不知道适合不适合我啊

第一趟
a b a b c a b c a c b a b
a b c a c

第二趟
a b a b c a b c a c b a b
a b c a c

第三趟
a b a b c a b c a c b a b
a b c a c 这趟为什么不从b开始啊而从a开始呢，上趟不从哪里不匹配从哪里开始吗？
完成匹配，跳出

假设子串为 'p1 p2 p3 p4.......pm '
对于第j个字符，有next[ j ] =
(1) 0 (j=1)
(2) Max{ k | 1<k<j && ' p1...p k-1 ' = ' p j-k+1...p j-1 ' }
(3) 1 其他情况

没有大括号就是不方便。哎，上面的算式是不是把你弄晕了呀？没关系，下面我介绍一种偷懒的方法

我就以

子串 a b a b a a b a b
next[j] 0 1 1 2 3 4 2 3 4 /*这里得数字代表什么啊next[j]得作用是什么啊*/

为例 来讲下
next[j] 里面 开头的红色01 是固定格式.

我就以兰色的4 来说明下为什么是4.
与4有关的, 是4所对应的兰色a之前的所有的字符,即紫色的 a b a b a
这个字符串中所有符合匹配条件的字符串如下
a b a b a a b a b a
a a
a b a a b a 最长的匹配字符串(a b a b a本身除外)在这里 ,长度为3, 再加上1,就是4了
注意next[ j ]中4 的位置!
next[ j ]中其他位置的数值也可以用同样的方法得出

为什么next[j]开头为固定的01？这个问题不太好回答。
最开头的next[j]是由子串第一个字符前面的字符来决定的，但那不存在，因此第一个next[j]的值为0
第二个next[j]是由第一个字符决定的，由于他是自己与自己比较，一定相等，所以值为1。
这样说可能有点牵强。那么我们来看看下面，可能会明白些，也更加了解next[j]到底是起什么作用的。

子串 a b a b a a b a b
next[j] 0 1 1 2 3 4 2 3 4
匹配子串长度 1 2 3 4 5 6 7 8 9 （对应位置 也可看成是截止到当前字符的子串串长）
最大右移 1 1 2 2 2 2 5 5 5 （当前字符不匹配时，子串最大右移距离）

我们发现，最大右移 + 对应的next[j] = 匹配子串长度，我估计这就是为什么要引入next[ j ] 这个参量，为了方便计算最大右移。不过对于next[j]的官方具体定义我没找到，望高人相告，在下先谢过了。

事实上，KMP算法还是有改进余地的，我们一直都在避免讨论这样一种情况:
a b c d e a
0 1 1 1 1 1
当a不匹配时，能向右最大移动几位呢？答案是6位，a 所能移动到的位置为a的下一位，即a 的右边一位
而根据next[j]计算出子串最大右移为6-1=5。这里他将a移动到a的位置上，然后做了一次无意义的比较（a = a ,a 与主串不匹配，那么显然a 与主串也不匹配）。这个问题我就不说了，虽然我有个改进方法，但这个问题还是留给大家去思考吧。

这一段看得我果然很郁闷啊 看来还是很有差距啊！

[此贴子已经被作者于2006-7-14 10:27:39编辑过]

[此贴子已经被作者于2006-8-8 15:55:42编辑过]