Sunday算法深度解析：线性时间匹配，效率超越KMP与BM

动画演示Sunday字符串匹配算法——比KMP算法快七倍！极易理解！

之前我通过动画详细讲解了KMP算法（没看过的可以回去查看）。
这次我将继续用动画的方式向大家介绍另一种用过就会爱上的字符串匹配算法：周日算法希望大家喜欢！KMP算法代表了人类寻找具有线性时间复杂度的字符串匹配算法的重大成就。
此后，出现了许多类似的算法，例如BM算法和Sunday算法。
这些算法在时间复杂度上都达到了线性。
但在实际应用中，所需时间各不相同。
BM算法在实际应用中的效率已经达到KMP算法的四五倍。
Sunday算法的效率优于BM算法。
如果你了解了这两个算法，你会发现Sunday算法相对于BM算法来说非常容易理解。
好了，对周日算法的赞美就到此为止，那么我们进入正题吧！注：以下将匹配字符串称为文本字符串，将匹配字符串称为模式字符串。
为什么周日算法这么容易理解？因为它只比暴力匹配算法多了一步！废话不多说，先给大家展示一下我精心制作的GIF动画：正如你所看到的，我们只移动了3次，就立刻得到了最终的结果。
Sunday算法是一种前后匹配算法（back-to-frontBM算法）。
当匹配失败时，焦点位于参与匹配的字符串中的下一个字符到最后一个字符。
Sunday的算法最有创新之处在于，在检测到匹配失败后，可以直接检查参与匹配的文本字符串中的下一个字符到最后一个字符。
在Python代码中，我们使用字典来存储模式串中每个字符最后一次出现的索引，这样前期只需要O(M)，M是模式串的长度即可完成初始设置，然后查询它O(1)。
同时，为了防止溢出，我在下面贴出的Python代码中手动在字符串末尾添加了字符'\0'。
代码非常简单。
我创建了一个类来在同一样式字符串中重用其位置字典并简化代码。
完成代码后，我对KMP算法和Sunday算法的匹配时间做了粗略的测试。
测试结果如下：太棒了！Sunday算法的平均匹配速度大约是KMP算法的七倍！为KMP和Sunday都创建一个对象，然后生成一个长度为100,000的随机字符串一次一个字母开始连续匹配。
创建-->匹配这个过程重复一百次，最后计算平均时间。
如果有人觉得不舒服，我会在下面发布一个披露代码。
您可以自己修改测试并立即使用！最后，如果您觉得这篇文章对您有帮助，请点赞并阅读！我会持续更新对大家有用的文章！我是洛阳，感谢您的光临！

算法：正则表达式匹配

让我们实现一个函数来匹配包含“.”的正则表达式和'*'。
字符“.”模式中的代表任意字符，“*”代表其前面的字符可以出现任意次数（包括0次）。
在这个问题中，匹配意味着字符串的所有字符都与整个模式匹配。
例如，字符串“aaa”匹配模式“a.a”和“ab*ac*a”，但不匹配“aa.a”或“ab*a”。