算法(四)(转载)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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券