正文

好了，赞美周日算法就到此为止，言归正传吧！

PS：下面将匹配字符串称为文本字符串，将匹配字符串称为模式字符串。

为什么周日算法这么容易理解？

因为它只比暴力匹配算法多了一步！

废话不多说，直接上我精心制作的GIF动画：

可以看到，我们只移动了3次，就直接找到了最终的结果。

Sunday算法是从前到后的匹配算法（BM算法是从后到前）。当匹配失败时，焦点位于参与匹配的文本字符串中最后一个字符的下一个字符。

动画演示Sunday 字符串匹配算法比KMP 算法快七倍

如果该字符没有出现在模式串中，则直接跳过，即移位位数=模式串长度+1。否则，移位位数=模式串长度-最右边位置字符（从0开始）=模式串中字符最右边位置到尾部的距离+1。Sunday算法最巧妙的地方在于，它发现匹配失败后，可以直接检查下一个字符参与匹配的文本字符串中最后一个字符的位置。

在Python代码中，我们使用字典来存储模式字符串中每个字符最后一次出现的索引。这样前期只需要O(M)，M为模式串的长度即可完成前期准备，然后进行查询。这是O(1) 时间。

同时，为了防止越界，我在下面贴出的python代码中手动在字符串末尾添加了一个’\0’字符。

代码

class Sunday(object): def __init__(self, pattern:str): # 模式字符串及其长度self.pattern, self.length=pattern, len(pattern) # 基于模式字符串构建的偏移字典self.shift_dict={ } # 为索引构建字典，值在enumerate(pattern): self.shift_dict[value]=self.length – 索引def match(self, text:str): i=0 text_length=len(text) text +=’\0 ‘ while i=text_length – self.length: j=0 while self.pattern[j]==text[i + j]: j +=1 if j=self.length: return i offset=self.shift_dict[text[i+ self. length]] if text[i+self.length] in self.shift_dict else self.length + 1 i +=offset return -1s=Sunday(‘nihao’)print(s.match(‘dasoijfoasjdoifjasdoifjoinihao’)) 代码它是很简单。同时，我构建了一个类，以在同一模式字符串下重用其位置字典并简化代码。

Sunday算法与KMP算法大比拼

写完代码后，我对KMP算法和Sunday算法的匹配时间进行了粗略的测试。测试结果如下：

太神奇了！Sunday算法的平均匹配速度大约是KMP算法的七倍！

KMP和Sunday分别构造一个对象，然后每次生成一个长度为10万个字符的随机字符串，开始匹配。

生成-匹配这个过程循环一百次，最后计算出平均时间。如果有人觉得不放心，我会在下面放出检测代码。您可以自己修改测试并立即使用！

检测代码如下

类KMP(): def __init__(self, ss: str) – list: self.length=len(ss) self.next_lst=[0 for _ in range(self.length)] self.next_lst[0]=- 1 i=0 j=-1 while i self.length – 1: 如果j==-1 或ss[i]==ss[j]: i +=1 j +=1 如果ss[i]==ss[ j]: self.next_lst[i]=self.next_lst[j] else: self.next_lst[i]=j else: j=self.next_lst[j] self.pattern=ss def match(self, ss:str): ans_lst=[ ] j=0 for i in range(len(ss)): if ss[i] !=self.pattern[j]: j=self.next_lst[j] if self.next_lst[j] !=-1 else 0 if ss[i]==self.pattern[j]: j +=1 if j==self.length: return i + 1 – self.length return -1class Sunday(object): def __init__(self,pattern:str): #模式字符串及其长度self.pattern, self.length=pattern, len(pattern) # 基于模式字符串构建的偏移字典self.shift_dict={} # 为索引构建字典，值在enumerate(pattern): self.shift_dict [ value]=self.length – 索引def match(self, text:str): i=0 text_length=len(text) text +=’\0′ while i=text_length – self.length: j=0 while self.pattern[j ]==text[i + j]: j +=1 if j=self.length: return i offset=self.shift_dict[text[i+self.length]] if text[i+self.length] in self.shift_dict else self.length + 1 i +=offset return -1import randomimport timesunday=Sunday(‘helloworld’)kmp=KMP(‘helloworld’)kmp_average_time=0sunday_average_time=0for i in range(100): ss=”.join([ chr (random.randint(97, 122)) for _ in range(100000)]) st=time.process_time() sunday.match(ss) ed=time.process_time() sunday_average_time +=ed – st st=时间。 process_time() kmp.match(ss) ed=time.process_time() kmp_average_time +=ed – stprint(‘kmp 平均时间： {}’.format(kmp_average_time/100))print(‘周日平均时间： {}’. format(sunday_average_time/100))