字符串匹配算法问题

dbshy · 发表于 2008-5-28 19:14:41

您需要登录才可以下载或查看，没有账号？注册会员

×

谁能将一下KMP算法,详细讲一下思路,好久没用,生疏了,大牛来帮忙

版务信息：本贴由楼主自主结贴～

禾西 · 发表于 2008-5-28 19:18:11

你說正則嗎？＝＝a

字符 = ~/表達式/

其他看幫助吧 XD

dbshy · 发表于 2008-5-28 19:36:05

不是的,我问的是KMP算法,一般的for循环复杂度为O (mn),而
KMP算法的复杂度为O(n)

那位详细讲一下思路

柳之一 · 发表于 2008-5-28 19:46:32

太长，懒得打字。
http://baike.baidu.com/view/659777.htm
现成的，参考一下吧。
其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

系统信息：本贴由楼主认可为正确答案，66RPG感谢您的热情解答～

dbshy · 发表于 2008-5-31 18:14:39

感谢LS,正在上机调试中

dbshy · 发表于 2008-5-31 19:28:50

调试了好久才成功,俺的水平越来越差了,KMP和DP感觉差不多,复杂度低,但很难想

link006007 · 发表于 2008-5-31 19:33:14

其实数据结构和算法一直都很难{/dk}
写出来到时用的时候还不一定会想到它...

dbshy · 发表于 2008-5-31 19:45:08

LS的话让我想到了网络流算法