当前位置: 首页 > news >正文

字符串匹配基础上

单模式匹配算法,也就是一个字符串和另一个字符串进行匹配。

1. BF 算法

BF 算法中的 BF 是 Brute Force 的缩写,中文叫作暴力匹配算法,也加朴素匹配算法。从名字可以看出,这种方法很暴力,效率也不高,但是简单、好懂。

在要匹配的两个字符串中,一个称之为主串,一个称之为模式串。比如要在字符串中 A 中查找字符串 B,那么字符串 A 就是主串,字符串 B 就是模式串。子串的长度为 n,模式串的长度为 m,因为要在主串中查找模式串,所以有 n>m。

BF 算法的思想很简单,就是拿主串中起始位置分别为 $0, 1,\cdots n-m$ 长度为 m 的总共 n-m+1 个子串分别与模式串进行比较,看有没有能匹配上的

可以看到,每次我们都要比较 m 个字符,极端情况下总共要比较 n-m+1 次,所以算法的最坏情况时间复杂度为 O(m*n)。

可以看到,这个算法的时间复杂度很高,但在实际的开发中,它却是一个比较常用的字符串匹配算法。一者因为实际开发中两个字符串的长度都不会太长,而且也不会每次都需要比较 n-m+1 次;二者因为其算法实现起来非常简单,不容易出错,便于维护。这也就是我们常说的 KISS(Keep it Simple and Stupid) 原则。

2. RK 算法

RK 算法的全称叫作 Rabin-Karp 算法,是为了纪念它的两个发明者而这样命名的。 这个算法其实就是刚刚 BF 算法的升级版。

在 BF 算法中,每次都要对 m 个字符逐个进行比较,这就大大降低了算法的效率。这时候,我们引入哈希算法,对子串逐个求哈希值,然后与模式串的哈希值进行比较来判断两个子串是否匹配。在不考虑哈希冲突的情况下,数字之间的比较就非常快了。

但是,在计算子串哈希值的时候,我们依然需要遍历 m 个字符,算法整体的效率并没有提高。我们需要设计一个特殊的哈希函数来避免每次都要遍历 m 个字符,这样,算法的效率就会大大改善。

对此,我们将包含 K 个字符的子串用一个 K 进制数来表示,将这个 K 进制数转化为 10 进制数作为子串的哈希值。比如字符串都是由小写字母组成,那么 a-z 这 26 个字母就映射到 0-25,0 表示 a,1 表示 b,以此类推。将 K 进制的数转化为 10 进制只需要将 10 变为 K 即可,如下图所示。

这样计算哈希值的话相邻两个子串就有一定关系。

假设 $S[i]$、$S[i-1]$ 分别是起始位置为 $i$ 和 $i-1$ 的哈希值,而 $h[i]$ 为位置为 $i$ 处字符的的映射,那么就有:

$$S[i] = 26*(S[i-1]-26^{m-1}*h[i-1])+ h[i+m-1]$$

其中 $26^{m-1}$ 这个指数项可以事先计算出来放在一个数组中,当我们需要的时候,就从对应下标中取出来即可。

可以看到,计算哈希值的时候,我们只需要遍历一次主串即可计算出所有子串的哈希值,这部分时间复杂度为 O(n)。模式串和子串需要比较 n-m+1 次哈希值,这部分时间复杂度也为 O(n)。所以,RK 算法总的时间复杂度为 O(n)。

但是,如果模式串的长度很大,那么计算出来的哈希值就会超出计算机中整形数据可以表示的范围。这时候,我们就可以牺牲一下,允许出现哈希冲突,比如可以求所有字符的映射和等,这种情况下哈希值的范围就小很多了。此时,当两个子串哈希值相同时,我们需要再进一步确定二者本身是否是相同的。

参考资料-极客时间专栏《数据结构与算法之美》

获取更多精彩,请关注「seniusen」!

相关文章:

  • Curator教程(一)快速入门
  • 阿里云搭建hadoop集群服务器,内网、外网访问问题(详解。。。)
  • 枚举与switch组合使用
  • 如何用纯 CSS 创作一个货车 loader
  • 阿里云马劲:保证云产品持续拥有稳定性的实践和思考
  • C# 获取对象 大小 Marshal.SizeOf (sizeof 只能在不安全的上下文中使用)
  • Oracle-SQL*Plus 简单操作
  • thinkphp 使用paginate分页搜索带参数
  • Money去哪了- 每日站立会议
  • ethereumjs/merkle-patricia-tree-2-API
  • 腾讯音乐赴美IPO仅11亿美元,疑受科技股抛售和中美贸易战影响
  • 【quick-cocos2d-lua】 基本类及用法
  • mysql安装时无法启动服务解决方案
  • Linux初级运维(十五)——bash脚本编程之函数
  • Hystrix断路器在微服务网关中的应用
  • @jsonView过滤属性
  • [nginx文档翻译系列] 控制nginx
  • 《深入 React 技术栈》
  • 【Amaple教程】5. 插件
  • Create React App 使用
  • CSS魔法堂:Absolute Positioning就这个样
  • Git的一些常用操作
  • Java 网络编程(2):UDP 的使用
  • JavaScript/HTML5图表开发工具JavaScript Charts v3.19.6发布【附下载】
  • LintCode 31. partitionArray 数组划分
  • node.js
  • uva 10370 Above Average
  • 工作中总结前端开发流程--vue项目
  • 缓存与缓冲
  • 软件开发学习的5大技巧,你知道吗?
  • 三栏布局总结
  • 使用 QuickBI 搭建酷炫可视化分析
  • 数组大概知多少
  • 推荐一款sublime text 3 支持JSX和es201x 代码格式化的插件
  • 携程小程序初体验
  • Android开发者必备:推荐一款助力开发的开源APP
  • const的用法,特别是用在函数前面与后面的区别
  • 机器人开始自主学习,是人类福祉,还是定时炸弹? ...
  • ​【C语言】长篇详解,字符系列篇3-----strstr,strtok,strerror字符串函数的使用【图文详解​】
  • # centos7下FFmpeg环境部署记录
  • #多叉树深度遍历_结合深度学习的视频编码方法--帧内预测
  • $emit传递多个参数_PPC和MIPS指令集下二进制代码中函数参数个数的识别方法
  • (2)(2.10) LTM telemetry
  • (done) ROC曲线 和 AUC值 分别是什么?
  • (function(){})()的分步解析
  • (poj1.2.1)1970(筛选法模拟)
  • (附源码)基于SpringBoot和Vue的厨到家服务平台的设计与实现 毕业设计 063133
  • (简单) HDU 2612 Find a way,BFS。
  • (十八)用JAVA编写MP3解码器——迷你播放器
  • (五)c52学习之旅-静态数码管
  • (一)python发送HTTP 请求的两种方式(get和post )
  • (转)shell中括号的特殊用法 linux if多条件判断
  • ***检测工具之RKHunter AIDE
  • .cn根服务器被攻击之后
  • .NET BackgroundWorker