关键词:KMP; string; match;
字符串匹配是一个既古老又现代的问题,历久弥新。生信领域中字符串处理更是daily work。诸如bwa这般神一样的软件,本质上也是在解决字符串非精准匹配的问题。所以,从本文开始,我们陆续会分享一些对我们有用的字符串匹配算法。
目前计划是先讲三个算法:
KMP算法
字典树算法
AC自动机算法
今天介绍的是KMP算法,一种常用的字符串精准匹配算法。这个算法不是很直观,其关键就是两点:
图片来源:https://blog.csdn.net/shimadear/article/details/82967876
最后给出代码:
如果有任何问题欢迎交流!