微信号:farsight2013

介绍:华清远见教育集团 - 高端IT就业培训专家,专注于嵌入式/Android/物联网高端人才培养.12年口碑积累,10万多名研发工程师从这里走出!

字符串匹配算法之Sunday算法

2019-01-10 17:30 华清远见

我们第一次接触字符串匹配,想到的肯定是直接用2个循环来遍历,这样代码虽然简单,但时间复杂度却是Ω(m*n),也就是达到了字符串匹配效率的下限。于是后来人经过研究,构造出了著名的KMP算法(Knuth-Morris-Pratt算法),让我们的时间复杂度降低到了O(m+n)。


但现代文字处理器中,却很少使用KMP算法来做字符串匹配,因为还是太慢了。现在主流的算法是BM算法(Boyer-Moore算法),成功让平均时间复杂度降低到了O(m/n),而Sunday算法,则是对BM算法的进一步小幅优化。


KMP算法很多人看了一遍遍以后,对next[n]数组的理解还是有点困难(包括笔者),写代码的时候总是容易变成这种情况(/捂脸.jpg):


(切到网页):马冬梅


(切到编译器):马什么梅


(切到网页):马冬梅


(切到编译器):马冬什么


(切到网页):马冬梅


(切到编译器):什么冬梅


而Sunday算法,理解起来则是非常容易,同时极低的时间复杂度,让Sunday算法成为了笔者目前最常使用的字符串匹配算法。


算法解释

Sunday算法和BM算法稍有不同的是,Sunday算法是从前往后匹配,在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。


1.如果该字符没有在模式串中出现则直接跳过,即移动位数 = 模式串长度 + 1;


2.否则,其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。


下面举个例子说明下Sunday算法。假定现在要在主串”substring searching”中查找模式串”search”。


刚开始时,把模式串与文主串左边对齐:



结果发现在第2个字符处发现不匹配,不匹配时关注主串中参加匹配的最末位字符的下一位字符,即标粗的字符 i,因为模式串search中并不存在i,所以模式串直接跳过一大片,向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7,从 i 之后的那个字符(即字符n)开始下一步的匹配,如下图:



结果第一个字符就不匹配,再看主串中参加匹配的最末位字符的下一位字符,是’r’,它出现在模式串中的倒数第3位,于是把模式串向右移动3位(m - 3 = 6 - 3 = r 到模式串末尾的距离 + 1 = 2 + 1 =3),使两个’r’对齐,如下:



匹配成功。


详细代码(Java版)


我们来一步一步解释。



其中total为主串,part为模式串。



定义一个长为ASCII码长度大小的数组,用于存放存入匹配失败时模式串需要移动的长度。这里看到,除了part中不存在的字符,移动长度都直接是模式串长度+1;而part中存在的字符,则需要移动的长度则依次减小。


这也很好理解,因为我们匹配的是模式串首部位置+模式串长度+1位置的字母存在于模式串中的位置,这个位置越靠后,则整个模式串需要移动的距离就越短。



s为模式串首部在字符串的位置,一开始为0;j是模式串已经匹配了的长度,一开始也是0。



这里是最关键的代码了,咱们讲细一点。


1.首先循环继续的判定条件为s<=tSize-pSizes作为模式串首部在字符串的位置,加上pSize肯定要比tSize小,不然就越界了;


2.j是模式串已经匹配了的长度,匹配开始或者匹配失败后都要给j赋值为0,重新开始计数;


3.接下就是一个字符一个字符的比较的循环;


4.已经比较成功,则j加1;


5.如果j已经大于等于pSize,就返回模式串首部在字符串当前的位置;


6.这是最关键的一句,涉及到Sunday算法的核心,也就是模式串在主串中的“跳跃”,我们把这句代码分解一下就好理解的多。



一个例子


其实最关键的,就是要计算move[]数组中的各个值,我们来手动算一下。



然后进行匹配:


1.s = 0, j = 1时,匹配失败


total[s+pSize] = total[6] = i


move[i] = 7


s+=7


待匹配串为ing substring


2.s = 7 , j = 0 时,匹配失败


total[s+pSize] = total[13] = u


move[u] = 5


s+=5


待匹配串为substring


3.匹配成功


Sunday算法的缺点

看上去简单高效非常美好的Sunday算法,也有一些缺点。因为Sunday算法的核心依赖于move数组,而move数组的值则取决于模式串,那么就可能存在模式串构造出很差的move数组。例如下面一个例子:


主串:baaaabaaaabaaaabaaaa


模式串:aaaaa


这个模式串使得move[a]的值为1,即每次匹配失败时,只让模式串向后移动一位再进行匹配。这样就让Sunday算法的时间复杂度飙升到了O(m*n),也就是字符串匹配的最坏情况。


总结

当然,也不能因为存在最坏的情况就直接否定Sunday算法,大多数情况下,Sunday依然是一个简单高效的算法,值得我们熟练学习掌握。

原文:https://www.jianshu.com/p/2e6eb7386cd3

END


相关精彩推荐:


华清远见近300个项目获批教育部“产学合作协同育人项目”立项


近50人拿到万元高薪,计算机专业平均薪资高达13005元!


华清远见荣获2018回响中国“社会信赖职业教育品牌”





品质IT教育  尽在华清远见

更多精彩内容请关注我们


或微信搜索华清远见,即可关注我们

免费讲座 | 干货分享 | 程序员生活 | 就业招聘

高端IT就业培训专家

www.hqyj.com


 
华清远见 更多文章 Python夺贯!三大编程语言榜即将全部“失守”! 可穿戴医疗设备会成为下一个风口吗? 考研热“高烧不退”的背后,是持续上涨的弃考族们 2019寒假全国高校AI人工智能高级师资班,即将在京举办 11月高薪就业榜火爆出炉 大专学历也能拿15000高薪!
猜您喜欢 Docker系列文章---如何搭建带证书的Docker私有仓库 Android脱壳圣战之---如何脱掉"爱加密"家的保护壳 Flask Repo: Flask-Admin Google资深工程师深度讲解Go语言 【忠告】混日子的年轻人是没有未来的