小菜我反复看了KMP算法的思想要义
但是还是没办法理解
希望大神们能通俗易懂的阐述一下KMP算法的思想（源代码我有).

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

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

如果说是串A去匹配串B，普通的匹配速度慢因为它在匹配的某个位置的时候如果失败了，那么要A往后平移一个，从第一个字符开始重新匹配。而kmp可以往后平移更多的位，并且不需要从第一位重新开始，可以直接从某一个k位开始匹配（保证移动后前面已经是相同的了）
感觉没说清楚，凑活看吧

我只知道简单匹配法，是带有回溯的 不知道是不是你所说的朴素的模式匹配。
我所说的简单匹配法就是一直匹配到不相等然后回到主串与模式串匹配时主串的后一个开始与模式串匹配
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的值”，其实在匹配中，用到next函数的地方，都是已经匹配好的部分，也就是说target和Pattern在这部分是完全相同的，然后你再想一下为什么要求头和尾相同的数目（因为当>2时，Pattern这时要跳跃）

谢谢啊
有点理解了

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