子字符串查找----各种算法总结

优点:

暴力查找算法:实现简单且在一般情况下工作良好(Java的String类型的indexOf()方法就是采用暴力子字符串查找算法);

Knuth-Morris-Pratt算法能够保证线性级别的性能且不需要在正文中回退;

Boyer-Moore算法的性能一般情况下都是亚线性级别;

Rabin-Karp算法是线性级别;

缺点:

暴力查找算法所需时间可能和NM成正比;

Knuth-Morris-Pratt算法和Boyer-Moore算法需要额外的内存空间;

Rabin-Karp算法内循环很长(若干次算术运算,其他算法都只需要比较字符);

各种字符串查找算法实现的成本总结

算法

版本

最坏情况

一般情况

是否回退

正确性

额外空间需求

暴力算法

--

MN

1.1N

1

KMP算法

完整的DFA(博客中实现的方法)

2N

1.1N

MR

仅构造不匹配的状态转换

3N

1.1N

M

完整版本

3N

N/M

R

Boyer-Moore算法

启发式查找不匹配字符

MN

N/M

R

Rabin-Karp算法

蒙特卡洛算法

7N

7N

是*

1

拉斯维加斯算法

7N*

7N

1

* 概率保证,需要使用均匀和独立的散列函数。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

3959
来自专栏ml

nyoj-----幸运三角形

幸运三角形 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述         话说有这么一个图形,只有两种符号组成(‘+’或者‘-’...

30410
来自专栏bboysoul

1067: 成绩评估

描述:我们知道,高中会考是按等级来的。90~100为A; 80~89为B; 70~79为C; 60~69为D; 0~59为E。 编写一个程序,对输入的...

892
来自专栏Petrichor的专栏

leetcode: 85. Maximal Rectangle

From LeetCode 笔记系列 18 Maximal Rectangle [学以致用]:

2373
来自专栏Unity Shader

Shader初学笔记:等值线

http://www.cnblogs.com/lpcoder/p/7103634.html

6115
来自专栏算法与数据结构

数据结构 数组和广义表以及树的基本概念

2-1 设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为 (2分) 1...

2618
来自专栏AIUAI

Caffe2 - (二十五) Detectron 之 utils 函数(3)

7554
来自专栏王亚昌的专栏

A*算法C实现

参考 http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html 实现了A*算法,模拟了一下,...

992
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

1253
来自专栏数据结构与算法

1038 一元三次方程求解

1038 一元三次方程求解 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver ...

2888

扫码关注云+社区

领取腾讯云代金券