飘云阁

 找回密码
 加入我们

QQ登录

只需一步,快速开始

查看: 6420|回复: 16

[C/C++] KMP算法初探篇_内存特征码搜索学习记录脚印!!!

[复制链接]
  • TA的每日心情
    无聊
    2023-3-14 21:31
  • 签到天数: 74 天

    [LV.6]常住居民II

    发表于 2019-7-29 14:22:07 | 显示全部楼层 |阅读模式
    本帖最后由 huangyushun 于 2019-7-29 14:36 编辑

    特征码搜索算法继续优化_支持通配符_支持X86_X64_这次终于通过雷神表哥的测试认证!!!
    https://www.chinapyg.com/thread-98948-1-1.html
    (出处: 飘云阁(PYG官方论坛) )


    如果直接使用的话,推荐以前折腾的算法_因为实际使用测试过,更快一些l,
    这帖只是这两天把KMP真正搞懂了_之前总是半懂状态不敢玩,分享一下心得;

    应该是三位前辈无数次模拟暴力搜索的回溯从中总结出来的规律吧,真是不易而有趣的事.....
    KMP算法的思路折腾下来,有一点感触,就是将暴力搜索的传统死板思路进行到底....KMP的算法就是把暴力搜索对比的回溯尽力优化到最佳,
    而sunday跟KMP,个人感觉比较像一个身经百战的赌徒对上一个传统憨厚的古代人....

    KMP的核心(相对暴力搜索而评):
    1、主串递加对比后一路向前绝不回溯,
    2、而子串尽最大可能少回溯;
    3、完美利用了[顺序对比]推进后,得到的[已比部分],


    我之前卡在,
    为什么公共元素是前后缀,而不管中间?
    看着好像只是找上一个重复的字符,说什么最大公共元素?

    最关键的
    1-已匹配部分的前后缀最大公共元素表
    2-以及顺序推进或顺序拉回,记得必须顺序


    综上相当于模拟了一次,暴力算法逐步推进子串从头对比主串+1到已匹配成功的长度.
    找出子串重新对比主串+1的位置跟子串有多少相同的,我们接下来就无需继续对比这些了.
    大概就理解到这么多了.....



    有图有**:
    KMP初探.png

    可优化空间很大:
    AAA.png


    上源码_优化的先不发_大家折腾折腾,结合我之前玩sunday写的那些思路.
    KMP算法初探_源码_没有优化的.rar (589 Bytes, 下载次数: 13, 售价: 3 枚飘云币)
    强烈建议看图多动手抄_懒鬼请浪费币




    评分

    参与人数 3威望 +7 飘云币 +4 收起 理由
    dryzh + 5 + 2 赞一个,这个帖子很给力!
    wgz001 + 1 + 1 期待表哥最终版
    不破不立 + 1 + 1 黄裕顺,pyg有你更精彩!

    查看全部评分

    PYG19周年生日快乐!
  • TA的每日心情
    擦汗
    2019-1-14 15:45
  • 签到天数: 1 天

    [LV.1]初来乍到

    发表于 2019-7-29 15:07:56 | 显示全部楼层
    赞一个 1!感谢楼主分享~~~~~
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    奋斗
    2023-2-16 08:00
  • 签到天数: 50 天

    [LV.5]常住居民I

    发表于 2019-7-29 15:47:44 | 显示全部楼层
    新手学习中,感恩分享
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    开心
    昨天 21:58
  • 签到天数: 1461 天

    [LV.10]以坛为家III

    发表于 2019-7-29 18:02:38 | 显示全部楼层
    感谢楼主分享,学习。
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    慵懒
    7 天前
  • 签到天数: 1523 天

    [LV.Master]伴坛终老

    发表于 2019-7-30 06:47:47 | 显示全部楼层
    厉害啊,成果具有价值!
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

  • TA的每日心情

    2020-1-9 10:13
  • 签到天数: 136 天

    [LV.7]常住居民III

    发表于 2019-7-30 09:28:00 | 显示全部楼层
    新手学习中,感恩分享
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    奋斗
    2023-2-6 15:52
  • 签到天数: 4 天

    [LV.2]偶尔看看I

    发表于 2019-7-30 09:49:36 | 显示全部楼层
    感谢楼主的分享,新人学习中...
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    奋斗
    2022-10-20 11:09
  • 签到天数: 1125 天

    [LV.10]以坛为家III

    发表于 2019-7-30 10:05:54 | 显示全部楼层

    感谢楼主的分享,还在黑暗中摸索
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

  • TA的每日心情

    昨天 09:14
  • 签到天数: 711 天

    [LV.9]以坛为家II

    发表于 2019-7-30 11:22:51 | 显示全部楼层

    感谢楼主分享,学习
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    发表于 2019-7-30 12:27:33 | 显示全部楼层
    感谢楼主分享,学习
    PYG19周年生日快乐!
    回复 支持 反对

    使用道具 举报

    您需要登录后才可以回帖 登录 | 加入我们

    本版积分规则

    快速回复 返回顶部 返回列表