[考研|报考科大软院] 请问各位学哥学姐834软件工程中KMP算法的问题

明宗越 · 发布于 2013-05-07 15:42 · 2009 次阅读
2800
本帖最后由 明宗越 于 2013-5-7 15:54 编辑

看到834大纲说掌握串的基本概念，存储结构和相关的操作算法
其中的KMP算法看不太懂，求各路大神指点下这个KMP算法怎么理解。
顶 收藏 回复
转载文章时务必注明原作者及原始链接，并注明「发表于 软院网 RuanYuan.Net 」，并不得对作品进行修改。
共收到 10 条回复
2800
明宗越 · #2 · 2013-5-7 15:42:48  回复 支持 反对
自己给自己顶一下哈
2076
阎魔あい · #3 · 2013-5-7 16:07:29  回复 支持 反对
你发帖的内容我就没看懂。。。。。。。。。。。。。。。
1753
vo_ · #4 · 2013-5-7 16:24:41  回复 支持 反对
KMP算法。。我直接给略过去了。。好吧，其实串这一章，我也直接给掠过去了。。三四年之内834真题都没涉及这块内容，不过现在软院竞争越来越大，也保不准会考到，支持你刨根问底弄明白一切拦路虎

点评

明宗越
嗯，后来看的有点明白了  详情 回复 发表于 2013-5-11 06:33
1753
vo_ · #5 · 2013-5-7 16:24:45  回复 支持 反对
KMP算法。。我直接给略过去了。。好吧，其实串这一章，我也直接给掠过去了。。三四年之内834真题都没涉及这块内容，不过现在软院竞争越来越大，也保不准会考到，支持你刨根问底弄明白一切拦路虎
48
hslx111 · #6 · 2013-5-7 16:52:28  回复 支持 反对
不认为考试能出KMP这么高端的算法，看不懂的话推荐看看这篇文章：
http://blog.csdn.net/v_july_v/article/details/7041827
1979
小马 · #7 · 2013-5-7 17:13:44  回复 支持 反对
模式匹配算法说真心话考到的概率很小，不管是408还是别的院校，包括1800题里，模式匹配算法题都少得可能。建议最多弄懂方法就成，其实很简单，看一下严奶奶的配套视频。现在时间还早，建议如果基础不是很好，从头看一遍严奶奶的视频，讲得很细很好。对以后的学习都有很大帮助！

点评

明宗越
嗯，多谢学长指点  详情 回复 发表于 2013-5-11 06:34
2593
Destiny · #8 · 2013-5-7 21:11:54  回复 支持 反对
其实就是匹配失败后从哪一位开始匹配的问题吧。就是说要匹配的子串有个很特别的属性：1-n位和当前匹配位置前n个字符一样，那就从n+1位开始下一次匹配的位置。用一个数组记录这个滑动。匹配失败后就按照这个数组进行回缩。其实只要有Next数组的话KMP很简单，但是这个数组比较不好算。12341235。在5处匹配失败的话下次从4开始匹配。那么NEXT（8）=4。大概就是这个意思。我是这么觉得的。考完研到现在没有看过书，不知道记的对不对。

点评

明宗越
嗯，差不多明白了，多谢哈  详情 回复 发表于 2013-5-11 06:34
2800
明宗越 · #9 · 2013-5-11 06:33:44  回复 支持 反对
vo_ 发表于 2013-5-7 16:24
KMP算法。。我直接给略过去了。。好吧，其实串这一章，我也直接给掠过去了。。三四年之内834真题都没涉及这 ...

嗯，后来看的有点明白了
2800
明宗越 · #10 · 2013-5-11 06:34:24  回复 支持 反对
小马 发表于 2013-5-7 17:13
模式匹配算法说真心话考到的概率很小，不管是408还是别的院校，包括1800题里，模式匹配算法题都少得可能。建 ...

嗯，多谢学长指点
2800
明宗越 · #11 · 2013-5-11 06:34:45  回复 支持 反对
Destiny 发表于 2013-5-7 21:11
其实就是匹配失败后从哪一位开始匹配的问题吧。就是说要匹配的子串有个很特别的属性：1-n位和当前匹配位置前 ...

嗯，差不多明白了，多谢哈
回帖
B Color Image Link Quote Code Smilies
Command + Enter
本版积分规则
楼主相关话题
收藏
共收到 10 条回复
参与回复
快速回复 返回顶部 返回列表