前言在上一篇文章中，我以动画的形式详细讲解了KMP算法（没看过的同学可以回去看看）。这次我还是用动画来介绍另一种用过就会爱上的字符串匹配算法：Sunday算法。希望得到大家的喜欢、关注、收藏和转发！KMP算法是一个里程碑式的算法，它的出现宣告人类找到了时间复杂度为线性的字符串匹配算法。之后出现了很多字符串匹配算法，如BM算法、Sunday算法等。这些算法在时间复杂度上已经达到了线性时间。但是，实际应用所花的时间还是有区别的。BM算法在实际应用中的效率达到了KMP算法的四五倍。Sunday算法的效率甚至高于BM算法。而如果同时了解这两种算法的同学就会明白：相对于BM算法，Sunday算法真的很容易理解。文案行，周日算法的吹捧就此打住，开始正剧！PS：以下将匹配字符串称为文本字符串，将匹配字符串称为模式字符串。为什么星期天算法非常容易理解？因为它只比暴力匹配算法多了一步！话不多说，直接上我精心制作的GIF动图：可以看到，我们只移动了3次，就直接找到了最终结果。Sunday算法是一种从前到后的匹配算法（BM算法是从后到前）。当匹配失败时，焦点将放在参与匹配的文本字符串中最后一个字符的旁边的字符上。如果该字符没有出现在模式串中，则直接跳过，即移动位数=模式串长度+1。否则，其移动位数=模式串长度-字符最右位置（从0开始）=模式串中字符最右位置到末尾的距离+1发现匹配失败后在文本字符串中参与匹配的字符。在python代码中，我们使用字典来存储每个字符在模式串中的最后一个索引，这样前期只需要O(M)，而M为模式串长度的时间可以完成前期准备，然后查询是O(1)时间。同时，为了防止越界，我在下面贴出的python代码中，在字符串末尾手动添加了一个'\0'字符。CodeclassSunday(object):def__init__(self,pattern:str):#模式字符串及其长度self.pattern,self.length=pattern,len(pattern)#根据模式字符串建立偏移字典self.shift_dict={}#为index和valueinenumerate(pattern)建立字典:self.shift_dict[value]=self.length-indexdefmatch(self,text:str):i=0text_length=len(text)text+='\0'whilei<=text_length-self.length:j=0whileself.pattern[j]==text[i+j]:j+=1ifj>=self.length:returnioffset=self.shift_dict[text[i+self.length]]iftext[i+self.length]inself.shift_dictelseself.length+1i+=offsetreturn-1s=Sunday('nihao')print(s.match('dasoijfoasjdoifjasdoifjoinihao'))代码非常简单。同时，我构造了一个类，在相同的模式字符串下重用它的位置字典，以简化代码。Sunday算法与KMP算法的较量写完代码后，我对KMP算法与Sunday算法的匹配时间进行了粗略的测试。测试结果如下：太棒了！Sunday算法的平均匹配速度大约是KMP算法的七倍！为KMP和Sunday构造一个对象，然后每次生成一个100,000个字符的随机字符串，让他们开始匹配。Generate-->Match这个过程循环一百次，最后算出平均时间。如果有大佬不放心，我在下面放出检测代码，大家可以自己修改测试，马上就可以用！检测代码如下classKMP():def__init__(self,ss:str)->list:self.length=len(ss)self.next_lst=[0for_inrange(self.length)]self.next_lst[0]=-1i=0j=-1whilei
