算法（四）（转载）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

最后给出代码：

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