0.前言
上一篇文章中，简单介绍了BM算法：机器学习中的数值查找算法(5)——字符串查找算法(Boyer-Moore算法) – 每天进步一点点 (longkui.site)
Sunday算法与ＢＭ算法类似，它们的思想原理有一定的相似性，但是sunday算法的匹配速度比ＢＭ算法还要快。这篇文章简单介绍一下 Sunday算法。
1.算法原理
例如：在字符串中“We should working hard”中查找单词“work”。
（1）首先将被搜索字符串和搜索字符进行首字母对齐，如下图：
（2）虽然左对齐之后，第一位的字符相同，然而第二位不相等，因此搜索字符串需要向后移动。最简单的方式是“work”向后移动一位，然后从被搜索字符串的第二位又开始比较，显然这种方式效率太低。此刻若采用KMP算法，则是利用匹配部分的信息进行移动。而ＢＭ算法是按照从末尾开始比较。对于Sunday算法重要的是参考被搜索字符串与搜索字符串比较的后一位字符“h”，如下图所示：
（3）由于字符“h”也不在搜索字符串，因此直接可以略过字符“h”之前的比较，移动5位，得到结果如下：
（4）根据上图所示，可以看出移动位数之后首字母并不相等，且字符“d”后面的空格符并不在“work”之中，因此继续向后跳过，得到的结果如下图：
（5）因此依次比较得到最终匹配结果，如下图所示：
在Sunday算法的比较过程中最核心的点在于，如果当前匹配失败，则根据被搜索字符串与搜索字符串的对应部分的后面一个字符串作为跳转的依据，如果该字符串不在被搜索字符串中，则直接略过；如果该字符在搜索字符串中存在，则将该位置与被搜索字符串中的该字符串进行对齐，然后从头开始比较。
基于Sunday算法的字符串匹配，相对于其他字符串匹配算法，移除了很多无关的比较操作，在短文本中的匹配或许不够明显，但是对于越长的文本则效果越明显。