Windard +
Github Zhihu RSS

记录 KMP 算法

网上有很多介绍 KMP 算法的文章,但是都没有认真读懂,因为它实在晦涩奥妙。

所以对 KMP 一直是敬而远之的态度,不懂就算,不求甚解。但是今天在知乎上看到一篇介绍 KMP 算法的回答,用在 2020 新冠肺炎基因测序上 ,可以让基因组查找从 O(m*n) 的时间复杂度下降到 O(m+n) 的时间复杂度,如此巨大的提升空间,让基因测序更加快速,功德无量。

而且时间复杂度 O(m+n) 也就意味着字符串查找只需从头到尾遍历一遍,不回头,不走重复路,也符合我的人生态度。

所以还是值得好好研究一下。


headlogo   Windard

但行好事,莫问前程

Blog

Opinion

Project

页阅读量:  ・  站访问量:  ・  站访客数: