最新要闻
- 环球短讯!俄罗斯开发者1年拿不到钱!好好的微星AfterBurner被一场战争害死
- 盘点CES上让人耳目一新的小玩意:极具创意
- 参与美国“阿尔忒弥斯计划” 日本人将首次登陆月球:日期未定
- 2499元起 Redmi K60成了:京东好评率比iPhone 14更高
- 新动态:你能接受不?奔驰Smart精灵#1开启硬件订阅:座椅加热1299元
- 时讯:股价暴跌后!特斯拉最大华裔散户天天“炮轰”马斯克
- 环球今热点:手慢真无了 码已不全!森马羽绒/棉服大促:一百多到手
- 世界热讯:美菱推出“杀新冠冰箱”:灭杀率高达99.9% 已过权威认证
- 全球时讯:PS5主机应该横放还是竖放引热议 索尼:都可以
- 热点评!配第四代i-MMD 东风本田新款英仕派e:HEV官图发布:真大号思域
- 外观复刻iPhone 14 Pro!乐视手机S1 Pro标配8+128GB存储:自称5G小霸王
- 当前讯息:一加8钉子户上车一加11:真正上手那一刻被惊艳到了
- 每日消息!一加11成为最火爆的第二代骁龙8旗舰!李杰:友商都可以去查
- NVIDIA推出第5代MAX-Q技术:游戏本性能进一步提升
- 女子买200万豪车 亲友400箱礼花庆贺 整条街道都摆满了
- 每日热议!成功率100%!中国民营火箭谷神星一号五连胜:一箭五星
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
全球新动态:字符串匹配算法综述
字符串匹配算法综述
对于字符串匹配算法,是在日常学习和工作中最常遇到的问题,字符串匹配算法要求输入主串(string)和子串(pattarn),然后返回子串在主串中第一次出现的位置。进行字符串匹配是学习计算机科学与技术时算法基础的问题,字符串匹配在生活中的应用及其广泛。在如今这个数字化、信息化的时代,字符串匹配算法更是不可或缺的,如我们平时所使用的百度引擎搜索信息时,便是字符串匹配的应用。如今网络迅速发展,如果还想提高运算检索速度,仅通过对硬件的改善提升检索速率是远远不够的,所以,我们必须研发更快、更良好的字符串匹配算法,才能够提升人们在更多领域中对信息处理的速度。根据此,常见的字符串匹配还有: BF(Brute Force,暴力检索)算法,KMP (Knuth-Morris-Pratt算法)算法,BM (Boyer和Moore算法)算法,等等。
1 引言
【资料图】
什么是字符串匹配,字符串匹配的概念:是指一个字符串是否为另一个字符串的子串。我们将短的字符串称为模式串,将长的字符串称为文本串(图1-1):
图 1-1 字符串匹配
字符串A为主串,字符串B是字串,字符串B在字符串A中出现的位置为2,最终返回2。
我们再看另一个例子(图1-2):
图 1-2 字符串匹配示列
在这个例子中,字符串A中并不包含字符串B,因此返回 -1。
基于此,本文利用多个字符串匹配算法,依据时空复杂度(时间复杂度/空间复杂度)O(n),对不同的字符串匹配算法进行分析。
2 BF算法(Brute Force暴力算法)
2.1 BF算法简介
BF(Brute Force,暴力检索)算法是最直接的暴力匹配。暴力算法的主要思路是从主串第一个字符位置出发并与字串进行匹配,然后假设主串的第一个字符位置与子串的第一个字符位置一致,那么继续比较后续字符。若前二个字符都不相同,则子串由主串的第二个字符起,以此类推。相等则继续匹配,不相等则子串之间又再次进行匹配,直至子串之间全部匹配成功,若主串中含有子串,则匹配成功,若不含有子串,则匹配失败。
2.2 Brute Force暴力算法的基本原理
首先,从主串的第一位开始,把主串和子串的每个字符一一比较(图2-1):
图 2-1 BF算法一一比较
主串和子串的第一个字符明显不匹配,因此,从第二个字符开始比对(图2-2):
图2-2 BF算法匹配字符
二者匹配,继续比较(图2-3):
图2-3 BF算法再次匹配字符
主串的第三个字符位置两个字符不匹配,因此,将子串整体往后移一位,从主串的第三个字符串开始比较(图2-4):
图2-4 BF算法匹配字符后移
主串的第三个字符是b,子串的第三个字符也是b,两者相等,继续比较(图2-5):
图2-5 BF算法匹配字符比较[1]
主串的第四个字符是c,子串的第二个字符也是c,两者相等,继续比较(图2-6):
图2-6 BF算法匹配字符比较[2]
主串的第五个字符是e,子串的第五个字符也是e,两个字符串一样,字符串匹配完成,主串包含子串,子串在主串中出现的位置是2,返回2(图2-7):
图2-7 BF算法返回子串位置
2.3 利用python实现BF算法:
def BF(s, p):
"""
BF算法字符串匹配
"""
indies = []
n = len(s)
m = len(p)
for i in range(n - m + 1):
index = i
for j in range(m):
if s[index] == p[j]:
index += 1
else:
break
if index - i == m:
indies.append(i)
return indies
2.4 BF算法总结:
BF(Brute Force,暴力检索)算法是初学者最容易理解的算法,也是传说中的暴力检索算法,假设主串和子串的长度分别为A,B,则它时间复杂度很容易达到O(A*B)。时间复杂度较大。虽然时间复杂度较高,但很容易理解,很适合初学者进行学习。有时候它的时间复杂度也能达到O(A+B),所以,此算法依旧被大量使用。
3 KMP算法(Knuth-Morris-Pratt算法)
3.1 KMP算法简介
Knuth-Morris-Pratt算法是一种比较高效的字符串匹配算法,它也是找到子串出现在主串中第一次出现的位置。比如:mnmnmnp,那么nmn在其位置1处(字符串从0开始计数),np在其位置5处,我们第一时间想到的是暴力匹配,即BF算法。但利用BF算法会导致时间复杂度为O(m*n),而KMP算法保证了时间复杂度为O(m+n)。
3.2 KMP算法的基本原理:
KMP算法是一种字符串匹配算法,它是对朴素模式算法(暴力匹配)的改进。 我们先看朴素模式下是怎么进行字符串匹配的。假设我们有两个字符串,被匹配的大串称为 主串,要匹配的小串称为模式串(图3-1):
图3-1 KMP算法基本原理
发现x与c不同后,进行移动(图3-2):
图3-2 KMP算法开始匹配
a与x不同,再次移动(图3-3):
图3-3 KMP算法匹配判断
此时比较到了c与y,于是下一步移动成了下面这样(图3-4):
图3-4 KMP算法匹配结果
这次移动和前二次移动有什么差别呢这一次的移动和前二次的移动有所不同,前二次移动时,直接把子串的首字符和前一次主串比对在不同的位置对齐,而这次不是,原因是在这次移动前,y和c已经对齐,而y之前的ab又和子串的前缀ab相同,所以ab不需重新比较,而是直接在第三个位置进行比较(图3-5):
图3-5 KMP算法再次匹配
Kmp对于这种情况就直接使用当前所比较的字符串前面的最长相同前后缀。再将前缀与主串对齐,然后再比较后面的字符串的字符。这里,就到了KMP的核心思想了,如何确定子串中每个字符之前的最长相同前后缀(图3-6):
图3-6 KMP算法确定前后缀
在主串的每个字符下记录一个数字用来记录以这个字符结尾的最长前后缀相同子串长度。开始都记录为0,并且第一个字符确定为0,开始比对(图3-7):
图3-7 KMP算法进行对比
A与b和c都不同,所以b和c下数字都为0,a和a对齐(图3-8):
图3-8 KMP算法对比结果
此此时a与a相同,所以a底下的数值为1,也就是说比对相同的第一个字符下为1,b和b相同,因此b底下的数值为2,而c和a不同,此时上边的文字串不动,下边的文字串移动到当前比对地址即c的前一个的下方的数值的地方(图3-9):
图3-9 KMP算法规则位移
对于主串来说c的前一位是b,且下方所对应的数字为0,所以将子串的第0位与之前比对不匹配的位置对齐,即(图3-10):
图3-10 KMP算法再次匹配
子串位置如图所示,继续进行比对,比对到c与a时,发现主串与子串字符不匹配(图3-11):
图3-11 KMP算法出现不匹配
这时候,c和a不匹配,则比较子串所对应位置主串字符下的数字的位置(图3-12):
图3-12 KMP算法比较数字位置
也就是位置为2的地方与上面比对位置对齐(图3-13):
图3-13 KMP算法位置对齐
此时c与c相同,整个字符串自比对完成(图3-14):
图3-14 KMP算法自对比完成
如果匹配不成功,则对比主串前一字符下的数字的位置,这么做是为了要找到前一个字符位置下相同前缀中的最长相同前缀,比如刚才的例子(图3-15):
图3-15 KMP算法查找前缀
此时a前边是“abcab“,所以要找到”abcab“的最长相同前缀,就是ab(图3-16):
图3-16 KMP算法查找成功
然后再移动到ab与ab对其的位置继续比较即可。
3.3 利用python实现KMP算法,如下:
def compute_prefix_function(p):
m = len(p)
pi = [0] * m
k = 0
for q in range(1, m):
while k > 0 and p[k] != p[q]:
k = pi[k - 1]
if p[k] == p[q]:
k = k + 1
pi[q] = k
return pi
def kmp_matcher(t, p):
n = len(t)
m = len(p)
pi = compute_prefix_function(p)
q = 0
for i in range(n):
while q > 0 and p[q] != t[i]:
q = pi[q - 1]
if p[q] == t[i]:
q = q + 1
if q == m:
return i - m + 1
return -1
3.4 KMP算法总结
总的来说,就是找到子串中的每个字符的最长相同前后缀,如果子串的长度为a,那么主串的指向是一直向前移动,子串的指向也是向前的,所以最后的结果是长度为2a,时间复杂度则为O(a),KMP算法中运用了最长相同前后缀的方法进行比对,如果子串的长度为b,则KMP算法的时间复杂度为O(a+b),提高了算法效率。
4 BM算法(Boyer和Moore算法)
4.1 BM算法简介
BM (Boyer和Moore算法) 算法的执行效率较高,而且比较容易理解。常用一些软件中的快捷查找方法都是利用此算法。
4.2 BM算法的基本原理
我们用例子来了解BM算法的基本原理(图4-1):
图4-1 BM算法基本原理
第一步,将两个字符串左端对齐,从右端开始比对。S和E,通过此,便可以发现字符串不匹配。因此,我们便需要寻找一下子串中是否包含这个字符s,发现子串中并没有s,这时我们便需要将子串移动到主串s所对应的下一个位置(图4-2):
图4-2 BM算法移动子串位置
然后我们再次从字符串的尾部开始比对,发现子串尾部位置p和E不匹配,在子串中看是否存在p,子串中包含p,因此,便将主串和子串中p的位置对齐(图4-3):
图4-3 BM算法主、子串对齐
继续从尾部进行比较,发现E匹配,L匹配,P匹配,M匹配,但I和A不匹配,再次寻找子串中是否有I,此时发现主串中的E可以和子串中的第一个字符E对应,可直接将子串移动到两个E对应的位置(图4-4):
图4-4 BM算法字符匹配
然后继续从尾部开始比对,P和E不匹配,则看子串中是否包含P,存在,则移动子串的P和主串的P对应的位置对齐(图4-5):
图4-5 BM算法字符匹配对齐
再继续从尾部开始以一比对,匹配成功。
4.3 利用python实现BM算法:
def getBMBC(pattern):
#预生成坏字符表
BMBC = dict()
for i in range(len(pattern) - 1):
char = pattern[i]
#记录坏字符最右位置 (不包括模式串最右侧字符)
BMBC[char] = i + 1
return BMBC
def getBMGS(pattern):
#预生成好后缀表
BMGS = dict()
#无后缀仅限根据坏字移位符规则
BMGS[""] = 0
for i in range(len(pattern)):
#好后缀
GS = pattern[len(pattern) - i - 1:]
for j in range(len(pattern) - i + 1):
#匹配部分
NGS = pattern[j:j + i + 1]
#记录模式串中好后缀最靠右位置(除结果处)
if GS == NGS:
BMGS[GS] = len(pattern) - j - i - 1
return BMGS
def BM(string, pattern):
"""
Boyer-Moore算法实现字符串查找
"""
m = len(pattern)
n = len(string)
i = 0
j = m
indies = []
BMBC = getBMBC(pattern=pattern)
#坏后缀
BMGS = getBMGS(pattern=pattern)
#好后缀
while i < n:
while(j > 0):
if i +j -1 >= n:
#当无法继续向下搜索就返回值
return indies
#主串判断匹配部分
a = string[i +j - 1:i + m]
#模式串判断匹配部分
b = pattern[j - 1:]
#当前位匹配成功则继续匹配
if a == b:
j = j - 1
#当前位匹配失败根据规则位移
else:
i = i + max(BMGS.setdefault(b[1:],m),
j - BMBC.setdefault(string[i + j - 1], 0))
j = m
#匹配成功返回匹配位置
if j == 0:
indies.append(i)
i += 1
j = len(pattern)
4.4 BM算法总结:
BM (Boyer和Moore算法) 算法容易理解,且执行小路较高,是一种构思比较精巧的字符串匹配算法。BM算法与暴力算法和KMP算法不同,BM算法采用后缀比对法,其核心思想在于,通过坏字符算法和好后缀算法,找到子串每次后移的最大距离。BM算法开始将主串与子串头对齐,尾比对,如果尾部不同,则可一次确定比对失败,将子串进行位移。
5总结
BF(Brute Force,暴力检索)算法是初学者最容易理解的算法,也是传说中的暴力检索算法,时间复杂度较大。虽然时间复杂度较高,但很容易理解,很适合初学者进行学习。有时候它的时间复杂度也能达到O(A+B),所以,此算法依旧被大量使用。
kmp算法中,找到子串中的每个字符的最长相同前后缀, KMP算法中运用了最长相同前后缀的方法进行比对,如果主串的长度为a,子串的长度为b,则KMP算法的时间复杂度可记为为O(a+b),相对于暴力法,提高了算法效率。
BM算法采用后缀比对法,其核心思想在于,通过坏字符算法和好后缀算法,找到子串每次后移的最大距离。BM算法开始将主串与子串头对齐,尾比对,如果尾部不同,则可一次确定比对失败,将子串进行位移。
全球新动态:字符串匹配算法综述
新资讯:网易云音乐用户画像资产治理及业务赋能
每日热议![概率论与数理统计]笔记:3.1 随机向量的分布
环球短讯!俄罗斯开发者1年拿不到钱!好好的微星AfterBurner被一场战争害死
盘点CES上让人耳目一新的小玩意:极具创意
参与美国“阿尔忒弥斯计划” 日本人将首次登陆月球:日期未定
2499元起 Redmi K60成了:京东好评率比iPhone 14更高
新动态:你能接受不?奔驰Smart精灵#1开启硬件订阅:座椅加热1299元
环球播报:软件开发入门教程网之C++ 引用
[笔记]斜率优化
HTML超文本标记语言2
时讯:股价暴跌后!特斯拉最大华裔散户天天“炮轰”马斯克
环球今热点:手慢真无了 码已不全!森马羽绒/棉服大促:一百多到手
世界热讯:美菱推出“杀新冠冰箱”:灭杀率高达99.9% 已过权威认证
全球时讯:PS5主机应该横放还是竖放引热议 索尼:都可以
热点评!配第四代i-MMD 东风本田新款英仕派e:HEV官图发布:真大号思域
世界视点!【操作系统实验/Golang】实验4:虚拟内存页面置换算法
世界时讯:Python工具箱系列(二十二)
初识Vue
环球消息!ACWING 4261. 孤独的照片
外观复刻iPhone 14 Pro!乐视手机S1 Pro标配8+128GB存储:自称5G小霸王
当前讯息:一加8钉子户上车一加11:真正上手那一刻被惊艳到了
每日消息!一加11成为最火爆的第二代骁龙8旗舰!李杰:友商都可以去查
NVIDIA推出第5代MAX-Q技术:游戏本性能进一步提升
女子买200万豪车 亲友400箱礼花庆贺 整条街道都摆满了
当前热议!无监控,不运维!深入浅出介绍ChengYing监控设计和使用
学习笔记——在IDEA中创建Maven版的web工程;框架;Mybatis简介;搭建Mybatis框架步骤
每日热议!成功率100%!中国民营火箭谷神星一号五连胜:一箭五星
今日热闻!33岁男子酗酒20年骨头坏死:13岁开始喝、每天至少半斤
动画版口碑崩盘 《三体》国产剧版过审获许可证 最快本月上线腾讯视频
世界速递!特斯拉最大散户投资者成马斯克头号反对者:连续多日公开炮轰
关注:一步一步实现若依框架--2.2实现后台限流rate_limiter
最资讯丨ACWING 4645. 选数异或
天天要闻:全球第四大汽车制造商CEO:欧洲中产阶级将选购中国汽车
清华应届硕士炮轰字节恶意低薪:月薪2万 硕士白读还倒贴
世界快看:面试官:数据库日期类型字段,需要兼容不同数据库,应该如何选择?
今日最新!ThreadLocal源码解析及实战应用
交换机二层组播配置
管理工具造成的阻塞
前沿热点:国产战机大片!电影《长空之王》定档:今年五一上映
杭州外来人口占3成 河南人数比肩本地土著 原来有历史原因
小米13系列大卖、汽车售价可达35万以上 小米高端成了:股价大涨
采埃孚新安全带:不用开空调 可提升电动车15%续航
焦点速读:3999元起 一加11首销51分钟打破所有二代骁龙8销量、销售额双记录
家用光纤宽带多少兆合适?家用光纤怎么接路由器?
招财猫的原型是什么猫?招财猫左手右手分别代表什么?
修正液的成分是什么?修正液的性质有哪些?
丁克家族是什么意思?丁克家庭的好处和坏处有哪些?
纪宝贝是什么电视剧的角色?纪宝贝是什么品种的狗?
印度首家旗舰店来了?传苹果(AAPL.US)开始招聘零售店员工
年终盘点丨最受开发者欢迎的文章 TOP20
天天快报!华硕ROG首款DP2.1接口显示器发布:无压缩4K 160Hz画质
世界热讯:车主激烈维权上演0元购!特斯拉成都门店否认:都是理性维权
重达2.4吨!美国40年前发射卫星今日坠落地球:或为朝鲜半岛
行业最低!一加Buds Pro 2首销899元:全链路延时仅54ms
【全球独家】腾讯发布未成年人春节寒假限玩通知:春节7天全开 工作日继续禁玩
京音平台-一起玩转SCRM之电销系统
全球滚动:特斯拉降价 国外车主怎么就不闹:原因发人深思
环球观速讯丨电视“套娃式充会员”吃相难看 有人呼吁建立互相兼容的会员体系
天天要闻:电子后视镜正式获批!吉利路特斯首批上车:选装费1万6
北斗三号卫星系统总设计师:北斗核心指标已超GPS
精选!极端暖冬席卷欧洲 多国冬天“入夏”:天然气价格也遭暴跌
环球热门:深拷贝、浅拷贝
6.Servlet
环球短讯!春节档电影票房乐观预测可达85亿 吴京主演《流浪地球2》领跑
每日焦点!支付宝2023年“集五福”来了 网友:两块钱的大项目
时讯:网站关停!广汽讴歌成为历史 正式退出中国市场
2023中国航天开门红!我国再次成功发射一箭三星
卢伟冰:Redmi K60卖的非常好 是2.5K-4K价位首选!
天天即时看!未来要取代iPhone!苹果AR/VR头戴设备将春季发布:原型机已发放
A16研发失败后!iOS 17首曝光:苹果挤牙膏 没重大更新让人失望
天天讯息:电源买双倍功率就中计啦!大可不必
全球观热点:用4年依旧流畅!一加11今日首销:最低12G内存 3999元起
焦点速讯:暴雪网易复合几乎不可能:不会降低标准 正和新代理谈的火热
4week-3字符串和字符
世界时讯:DVWA靶场实战(五)——File Upload
ACWING 4366. 上课睡觉
【世界速看料】NVIDIA正在开发AI优化驱动:性能飙升30%
大几千元的空气消毒机是智商税吗?这操作多少有点愣
世界信息:神奇的雌雄同体:一不小心 “老婆”变成“老公”
[1] LeetCode 刷题笔记: 两数之和 [S]
expres实现登录与修改密码
《鹿鼎记》主演时隔24年重聚:小宝的四个老婆 她几乎没变
Codeforces 1671 F Permutation Counting 题解
关注:如何优雅地校验后端接口数据,不做前端背锅侠
《中国奇谭》封神:上线仅三集 追番量破200万
红旗正式发布新能源品牌:全新LOGO 新车3秒破百
【环球新视野】学习笔记——Maven的核心概念之仓库、坐标;maven的依赖管理;Maven中统一管理版本号;Maven的继承;Maven的聚合
jmap——Java内存分析工具
全球消息!AMD锐龙7040砍掉没用的PCIe 5.0!内存翻番256GB
全球快看点丨微软Xbox老大斯宾塞盛赞索尼:无障碍手柄是对PS生态很好的补充
环球观热点:1.Maven入门
每日快播:特斯拉的好日子 到头了
全球热资讯!马斯克承诺成空谈!推特被裁员工仅获1个月工资补偿
中国空间站能量粒子探测器成功安装:自主研发 将开启10年运行
世界快报:Steam特别好评!PC策略大作《文明6》打0.9折:入正绝佳时机
20万天价酒店被抢光!春节旅游十大热门目的地公布
当前讯息:美国能源部出手 阿贡开发出全新锂硫电池:能量密度可达特斯拉4680十倍
看热讯:网约车带走3岁孩子妈妈一路狂追 司机委屈:不敢从反光镜看女乘客
精选!C++ TinyWebserver 部署到Linux下,并运行(使用的是Vmware的虚拟机运行Ubuntu20.04)