字符串搜索算法

字符串搜索算法(String searching algorithms)又称字符串比对算法(string matching algorithms)是一种搜索算法,是字符串算法中的一类,用以试图在一长字符串或文章中,找出其是否包含某一个或多个字符串,以及其位置

下表为常见的算法以及其复杂度的对比

其中n为被搜索字符串长度,m为搜索子串长度

朴素算法(naive string-matching algorithm)

最普通的算法

预处理 - 0

匹配时间 - Θ(mn)


Rabin-Karp算法

预处理 - Θ(m)

匹配时间 - O((n-m)m


有限自动机(Finite Automata)

这个一般用来实现非回溯的正则表达式

预处理 - Θ(mk)

匹配时间 - Θ(n)


克努斯-莫里斯-普拉特算法(KMP)

预处理 - Θ(m)

匹配时间 - Θ(n)


Boyer-Moore字符串搜索算法-BM算法

预处理 - Θ(m)

匹配时间 - Θ(n)


Sunday字符串搜索算法

预处理 - Θ(m)

匹配时间 - Θ(n)


算法选择优先级 sunday > bm > kmp



上一篇: 拓扑排序
下一篇: KMP算法
作者邮箱: 203328517@qq.com