KMP算法初探篇_内存特征码搜索学习记录脚印!!!
本帖最后由 huangyushun 于 2019-7-29 14:36 编辑特征码搜索算法继续优化_支持通配符_支持X86_X64_这次终于通过雷神表哥的测试认证!!!
https://www.chinapyg.com/thread-98948-1-1.html
(出处: 飘云阁(PYG官方论坛) )
如果直接使用的话,推荐以前折腾的算法_因为实际使用测试过,更快一些l,
这帖只是这两天把KMP真正搞懂了_之前总是半懂状态不敢玩,分享一下心得;
应该是三位前辈无数次模拟暴力搜索的回溯从中总结出来的规律吧,真是不易而有趣的事.....
KMP算法的思路折腾下来,有一点感触,就是将暴力搜索的传统死板思路进行到底....KMP的算法就是把暴力搜索对比的回溯尽力优化到最佳,
而sunday跟KMP,个人感觉比较像一个身经百战的赌徒对上一个传统憨厚的古代人....{:titter:}
KMP的核心(相对暴力搜索而评):
1、主串递加对比后一路向前绝不回溯,
2、而子串尽最大可能少回溯;
3、完美利用了[顺序对比]推进后,得到的[已比部分],
我之前卡在,
为什么公共元素是前后缀,而不管中间?
看着好像只是找上一个重复的字符,说什么最大公共元素?
最关键的
1-已匹配部分的前后缀最大公共元素表
2-以及顺序推进或顺序拉回,记得必须顺序
综上相当于模拟了一次,暴力算法逐步推进子串从头对比主串+1到已匹配成功的长度.
找出子串重新对比主串+1的位置跟子串有多少相同的,我们接下来就无需继续对比这些了.
大概就理解到这么多了.....
有图有**:
可优化空间很大:
上源码_优化的先不发_大家折腾折腾,结合我之前玩sunday写的那些思路.
强烈建议看图多动手抄_懒鬼请浪费币
赞一个 1!感谢楼主分享~~~~~ 新手学习中，感恩分享 感谢楼主分享，学习。
厉害啊，成果具有价值！ 新手学习中，感恩分享 感谢楼主的分享，新人学习中...{:biggrin:}
感谢楼主的分享，还在黑暗中摸索
感谢楼主分享，学习 感谢楼主分享，学习
页:
[1]
2