关于KMP算法的理念

你先了解一下朴素的模式匹配算法。
KMP算法是基于朴素的算法并去掉了回溯，所以效率变得很高。

不知道你了解到什么程度：
1. 朴素的模式匹配算法会带有回溯，这种现象你是否理解？
2. KMP的匹配过程，你是否了解？

我只知道简单匹配法，是带有回溯的 不知道是不是你所说的朴素的模式匹配。
我所说的简单匹配法就是一直匹配到不相等然后回到主串与模式串匹配时主串的后一个开始与模式串匹配
KMP的过程  我是了解一点
麻烦你讲一下KMP怎么去掉回溯的
其实书上的内容我有看过几遍了
但是还是不能理解吃透
所以想找一个通俗易懂的方法理解

举个例子：

Target:  acabaabaabcacaabc
Pattern: abaabcac

Step1:
T: a c a b a a b a a b c a c a a b c
P: a b a a b c a c

Step2:
T: a c a b a a b a a b c a c a a b c
P:     a b a a b c a c

Step3:               
T: a c a b a a b | a a b c a c a a b c
P:     a b a a b | c a c

Step1 - Step3 与朴素匹配无差别，关键Step4
显然，如果用朴素匹配方法
a b a a  !=  b a a b           ------必然失配
a b a  !=  a a b  -----------必然失配
a b  ==  a b   -----------有匹配的可能

Step4:
T: a c a b a a b a a b c a c a a b c
P:           a b a a b c a c

从这里你可以看出，此次KMP匹配省掉了两次必然失配的匹配过程。

总之，关键是找出Pattern的特征函数
下面举例来说明如何求一个pattern的next特征函数
Pattern：a b a a b c a c
令 j 表示失配的位置。例如，j = 0 ，即在第0位（Pattern的a处）发生失配。
现在开始计算：
j = 0 ：next(j) = -1, 表示一开始就发生失配，target向右移一位，Pattern从0开始。
j = 1：next(j) = 0, 表示其他情况，target保持不动， Pattern从0开始
j = 2：next(j) = 0, 表示其他情况，target保持不动， Pattern从0开始
j = 3：next(j) = 1, 表示前面1位（a）= 后面1位（a），target保持不变，Pattern从1开始匹配。
j = 4：next(j) = 1, 表示前面1位（a）= 后面1位（a），target保持不变，Pattern从1开始匹配。
j = 5：next(j) = 2, 表示前面2位（ab）= 后面2位（ab），target保持不变，Pattern从2开始匹配。

也即，从头开始并同时从尾开始比较，看看头尾有多少连续的位相同

关键是明白模式的next特征函数，其他都很简单。

[ 本帖最后由 hzh512 于 2010-8-3 16:40 编辑 ]

你可以想一下为什么“从头开始并同时从尾开始比较，看看头尾有多少连续的位相同，其数目就是next的值”，其实在匹配中，用到next函数的地方，都是已经匹配好的部分，也就是说target和Pattern在这部分是完全相同的，然后你再想一下为什么要求头和尾相同的数目（因为当>2时，Pattern这时要跳跃）

有需要的可以访问：
https://hi.bccn.net/space.php?uid=369206&do=blog&id=17739