Project1

标题: 字符串匹配算法问题 [打印本页]

作者: dbshy 时间: 2008-5-28 19:14
标题: 字符串匹配算法问题
谁能将一下KMP算法,详细讲一下思路,好久没用,生疏了,大牛来帮忙 [LINE]1,#dddddd[/LINE]版务信息：本贴由楼主自主结贴～

作者: 禾西 时间: 2008-5-28 19:18
你說正則嗎？＝＝a

字符 = ~/表達式/

其他看幫助吧 XD

作者: dbshy 时间: 2008-5-28 19:36
不是的,我问的是KMP算法,一般的for循环复杂度为O (mn),而
KMP算法的复杂度为O(n)

那位详细讲一下思路

作者: 柳之一 时间: 2008-5-28 19:46
太长，懒得打字。
http://baike.baidu.com/view/659777.htm
现成的，参考一下吧。
其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。
[LINE]1,#dddddd[/LINE]系统信息：本贴由楼主认可为正确答案，66RPG感谢您的热情解答～

作者: dbshy 时间: 2008-5-31 18:14
感谢LS,正在上机调试中

作者: dbshy 时间: 2008-5-31 19:28
调试了好久才成功,俺的水平越来越差了,KMP和DP感觉差不多,复杂度低,但很难想

作者: link006007 时间: 2008-5-31 19:33
其实数据结构和算法一直都很难{/dk}
写出来到时用的时候还不一定会想到它...

作者: dbshy 时间: 2008-5-31 19:45
LS的话让我想到了网络流算法

欢迎光临 Project1 (https://rpg.blue/)