关于KMP算法的理念 - 数据结构与算法

编程论坛 → 开发语言 → 『数据结构与算法』 → 关于KMP算法的理念

标题：关于KMP算法的理念

取消只看楼主

aizuoai123

等　级：论坛游民
帖　子：44
专家分：36
注　册：2010-5-14
结帖率：100%

楼主

已结贴√ 问题点数：20 回复次数：4

关于KMP算法的理念

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

搜索更多相关主题的帖子: KMP　算法　理念　

2010-08-03 12:56

aizuoai123

等　级：论坛游民
帖　子：44
专家分：36
注　册：2010-5-14

第 2 楼

得分:0

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

2010-08-03 16:13

aizuoai123

等　级：论坛游民
帖　子：44
专家分：36
注　册：2010-5-14

第 3 楼

得分:0

以下是引用朱涛在2010-8-3 16:03:22的发言：

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

因为我看过KMP的大概思路你说的我看的明白
但是那个保证易懂后前面的是相同的这个代码能说说明白点么

2010-08-03 16:16

aizuoai123

等　级：论坛游民
帖　子：44
专家分：36
注　册：2010-5-14

第 4 楼

得分:0

恩对的
就是对这个特征NEXT函数
不是太理解

2010-08-03 17:41

aizuoai123

等　级：论坛游民
帖　子：44
专家分：36
注　册：2010-5-14

第 5 楼

得分:0