专栏首页生信了算法(四)(转载)KMP算法

算法(四)(转载)KMP算法

关键词:KMP; string; match;

字符串匹配是一个既古老又现代的问题,历久弥新。生信领域中字符串处理更是daily work。诸如bwa这般神一样的软件,本质上也是在解决字符串非精准匹配的问题。所以,从本文开始,我们陆续会分享一些对我们有用的字符串匹配算法。

目前计划是先讲三个算法:

KMP算法

字典树算法

AC自动机算法

今天介绍的是KMP算法,一种常用的字符串精准匹配算法。这个算法不是很直观,其关键就是两点:

  1. 理解主串不用回溯,而需要对模式串求解next数组。
  2. 知道如何求解next数组。当我们知道了next[0], next[1], …, next[j]之后,如何求解next[j+1]呢。其关键就在于:当模式串的第j位与第next[j]位相同时,next[j+1]=next[j]+1;而两者不相同时,next[j+1]的求解就不断降级为看第j位是否与next[next[j]]位相同。由于next[j]比j要小,所以经过多次迭代后,总会收敛。那为什么可以这样“降级”呢?下面的图片有助于理解。

图片来源:https://blog.csdn.net/shimadear/article/details/82967876

最后给出代码:

如果有任何问题欢迎交流!

本文分享自微信公众号 - 生信了(gh_ed36a29a9a9d),作者:hxj7

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 序列比对(26)精准匹配之KMP算法、Trie树以及AC自动机

    之前的序列比对文章大都在利用动态规划算法解决字符串的非精准匹配(允许错配、插入和缺失),比如全局比对和局部比对问题。当然,后来我们还介绍了模序发现和中间字符串问...

    一只羊
  • (转载)Python的configparser模块

    做生信的同学在使用类Unix系统的时候,经常会接触配置文件(config)。就笔者自己的经验而言,配置文件的常见格式有如下几种:

    一只羊
  • R语言作图(一)violin plot

    即便小仙同学决定学习R语言来提升自己作图的“逼格”的时候,心中还有有些疑虑的(嘿嘿,我这么懒,可不愿意做无用功了?)。仔细想了想,貌似又找到了两个学习的理由。

    一只羊
  • KMP算法学习(详解)

    kmp算法又称“看毛片”算法,是一个效率非常高的字符串匹配算法。不过由于其难以理解,所以在很长的一段时间内一直没有搞懂。虽然网上有很多资料,但是鲜见好的博客能简...

    Angel_Kitty
  • 吃透洋葱模型

    作者:掘金@苏里 https://juejin.im/post/6844904025767280648

    zz_jesse
  • 超详细!从本质上搞懂困惑你多年的KMP匹配算法

    KMP算法是一种字符串匹配算法,可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。本文将引导您学习KMP算法。

    帅地
  • KMP算法浅析

    具体参见: KMP算法详解 背景: KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法...

    mukekeheart
  • 模式匹配KMP算法

    匹配到j=5时失效了,BF算法里我们会使i=1,j=0,再看s的第i位开始能不能匹配,而KMP算法接下来就去比较T[2](next[5]=2)和S[5]

    饶文津
  • c/c++补完计划(七): 哨兵节点

    SeanDepp
  • leetcode:83 删除排序链表中的重复元素

    问题? 如果next没有值的话,会报错的。 因为要相等啊,比较啊,有值才能比较是吧。 那为什么p.next=p.next.next;如果p.next.ne...

    用户7873631

扫码关注云+社区

领取腾讯云代金券