日志关键词筛选那件事，我又双叒叕卡住了。服务跑着跑着，要在一份几十万行的文本里快速定位某几个关键字，最初图省事直接用了朴素逐位匹配，结果数据量一上来，肉眼可见地慢。旁边同事随口说了一句“字符串匹配你试试Sunday算法呗”，我当时愣了一下——平时聊KMP、BM的人多，Sunday这名字倒是每次都在各种场合被带一嘴，但真正去抠过它实现细节的人还真不多。
后来我把Sunday算法的原理、代码、边界条件、和其他匹配算法的实测对比完整过了一遍，才发现这家伙属于“代码量极小、收益极大”的典型代表。今天把这套东西整理出来，从手算推导到工程落地，把该说的原理、该给的代码、该避的坑一次讲透。适合正在写文本处理、日志检索、编辑器查找功能，或者单纯想把字符串匹配这块地基打扎实的朋友。
1. 为什么是Sunday：它和KMP、BM差在哪
1.1 一个真实场景：字符串匹配把我卡住了
先交代下我遇到的实际问题。某个项目里需要把一批请求日志按关键字归类，日志文件单份大约10MB左右，里面要匹配的模式串有几十个，长度从几个字符到几十个字符不等。最开始我图省事，写了个两层循环的朴素匹配：外层遍历主串，内层逐位比对模式串，不相等就主串下标加1继续。跑完一次全量日志大概要两三百毫秒，看着不多，但是配合实时流式日志、每秒钟来好几批，CPU就有点吃不消了。
这种时候标准库的查找函数其实也能用，但我要做的不是单次查找，而是要对一段文本反复执行不同模式串的匹配，标准库每次调用都要重新做内部初始化，灵活性也不够。手写一个专用匹配器就成了更合理的选择。而Sunday算法，正是在这种场景下性价比最高的一类方案。
1.2 一个定位：Sunday是“坏字符规则的激进版”
字符串匹配算法大体分成两类：一类是“老老实实一步一步挪”，比如朴素算法；另一类是“失配之后根据某种规则尽量多跳几步”，比如KMP、BM、Horspool、Sunday都属于这一类。
KMP的核心是模式串的前后缀信息，失配时通过next数组让模式串自身滑动；BM和Sunday则是利用“主串中出现的字符”来决定跳多远。Sunday算法和BM的坏字符规则更接近，但它有一个特别朴素的想法：失配时不看已经匹配过的部分，而是直接盯住主串中“当前匹配窗口末尾的下一个字符”。这个字符一旦没有出现在模式串里，整个窗口可以直接跳过模式串长度再加1，效率一下子就上去了。
这说的就是Sunday算法：代码简单、平均性能好，特别适合文本搜索这种模式串短、主串长的场景。
2. 核心原理：失败之后，先盯着窗口外的一位
2.1 匹配主流程：怎么决定下一步跳多远
先用一句话说清Sunday的匹配思路：假设主串是S，模式串是P，当前对齐位置是i，也就是拿P[0]去对S[i]。如果从S[i]开始的m个字符和P完全一致，匹配成功；如果中途失配，Sunday不像KMP去前缀表里翻来翻去，而是直接看S[i + m]这个字符。
接下来分两种：
- 如果S[i + m]在模式串P里出现过，就把P中最后一次出现S[i + m]的位置，对齐到S[i + m]这个位置上。意思是下次从S[i + m - last]这个位置开始重新匹配。
- 如果S[i + m]压根不在P里，说明任何包含S[i + m]的窗口都不可能匹配成功，那就直接让对齐位置跳到i + m + 1。
这个“最后一次出现”非常关键。模式串里同一个字符可能出现多次，为了不漏掉潜在匹配，必须取最后一次出现的位置，这样移动量才是所有安全方案里最小的。如果取了第一次出现，移动量偏大，可能把后面真正能匹配上的位置跳过去。
2.2 偏移表：一次性预处理，搜索时查表
Sunday算法的效率全靠一张偏移表撑起来。预处理阶段遍历模式串，记录每个字符在模式串中最后一次出现时，距离模式串末尾还有多远。伪代码可以理解为：
对于模式串P，长度为m： 默认偏移 = m + 1 对每个字符P[k]，偏移表[P[k]] = m - k （后面的赋值会覆盖前面的，所以最后存的就是最后一次出现的位置）这也就是为什么预处理之后，匹配阶段每次失配都只需要查一次表，然后无脑让i += 偏移表[S[i + m]]。查表是O(1)的，整个匹配过程除了必要字符比较之外，几乎没有任何额外计算。
2.3 手推一个完整例子：从substring到search
光看理论不够直观，我们手算一遍。主串S = "substring searching algorithm"，模式串P = "search"。
先构建偏移表。P长度m=6，默认偏移为7。
| 字符 | 位置k | 偏移m-k |
|---|---|---|
| s | 0 | 6 |
| e | 1 | 5 |
| a | 2 | 4 |
| r | 3 | 3 |
| c | 4 | 2 |
| h | 5 | 1 |
然后开始匹配。
第一次对齐i=0，拿S[0..5]="substr"去比"search"。第1位s对s，第2位u对e，失配。看S[0+6]=S[6]='i'，'i'不在偏移表里，使用默认偏移7，i跳到7。
第二次对齐i=7，拿S[7..12]="ng sea"去比"search"。第1位n对s，失配。看S[7+6]=S[13]='r'，查偏移表，'r'的偏移是3，i跳到10。
第三次对齐i=10，S[10..15]正好是"search"，匹配成功，返回位置10。
整个过程中主串只比较了很少几轮，这就是Sunday“尽量多跳”的威力。
3. 代码落地：三种写法和它们的适用场景
3.1 标准实现：基于数组偏移表
最常见的实现方式是声明一个长度为256的数组作为偏移表。这里有一个非常容易犯的错：char类型在部分编译器下默认是signed，直接用s[i + m]做数组下标时，如果字符串里有大于127的字节（比如中文UTF-8编码的字节、二进制数据），会变成负数下标导致越界。所以查表前必须转成unsigned char。
一个标准实现如下：
#include <cstring> #include <vector> class SundayMatcher { public: explicit SundayMatcher(const std::string& pattern) : pattern_(pattern) { buildShiftTable(); } // 在text中查找第一次出现位置，找不到返回 -1 int search(const std::string& text) const { int n = static_cast<int>(text.size()); int m = static_cast<int>(pattern_.size()); if (m == 0) return 0; if (n < m) return -1; int i = 0; while (i <= n - m) { int j = 0; while (j < m && text[i + j] == pattern_[j]) { ++j; } if (j == m) { return i; } // 失配时看窗口末尾的下一个字符 if (i + m >= n) { return -1; } i += shift_[static_cast<unsigned char>(text[i + m])]; } return -1; } private: void buildShiftTable() { shift_.assign(256, static_cast<int>(pattern_.size()) + 1); int m = static_cast<int>(pattern_.size()); for (int k = 0; k < m; ++k) { shift_[static_cast<unsigned char>(pattern_[k])] = m - k; } } std::string pattern_; std::vector<int> shift_; };几个注意点：
shift_.assign(256, m + 1)把默认值设成了m + 1。这样任何没在模式串里出现过的字符，查表直接跳m + 1格。- 遍历模式串时，后面的字符会覆盖前面同字符的偏移值，天然实现了“最后一次出现位置”的需求。
- 内层比较用
text[i + j] == pattern_[j]，这里不要放任何额外逻辑，这一层就是纯粹的CPU密集型比较，越简洁越好。
3.2 找所有匹配：重叠与非重叠的处理差异
很多场景需要的不只是第一次出现，而是所有出现位置。最简单的做法是找到一次匹配后，把i加1继续找。这样做能保证不漏掉任何位置，包括重叠的匹配。
但如果你确认不需要重叠结果，可以做得更激进：匹配成功后，不看匹配窗口内部，而是直接查看窗口末尾的下一个字符所在的偏移，一次性跳过去。
std::vector<int> searchAll(const std::string& text) const { std::vector<int> result; int n = static_cast<int>(text.size()); int m = static_cast<int>(pattern_.size()); if (m == 0) return result; int i = 0; while (i <= n - m) { int j = 0; while (j < m && text[i + j] == pattern_[j]) { ++j; } if (j == m) { result.push_back(i); if (i + m >= n) break; // 非重叠版本：直接按下一个字符的偏移跳 i += shift_[static_cast<unsigned char>(text[i + m])]; } else { if (i + m >= n) break; i += shift_[static_cast<unsigned char>(text[i + m])]; } } return result; }这个版本匹配成功之后同样是跳偏移表，可能会跳过与上一个匹配重叠的匹配。比如在"aaa"里找"aa"，非重叠版本只会返回0，而重叠语义下应该返回0和1。需要哪种结果取决于业务：日志关键词过滤、敏感词扫描通常不需要重叠，文本高亮可能需要。我在实际项目里用的是非重叠版本，因为窗口扫描场景中重叠往往意味着业务上重复计数。
3.3 中文字符串和大字符集的适配
很多人一碰到中文就慌了，其实UTF-8编码下的中文字符串可以按字节直接匹配。原因是UTF-8是自同步编码，每个字符的字节序列边界是明确的，只要模式串是从合法字符边界截取的，按字节做Sunday匹配不会出现“半个汉字被误匹配”的问题。
但有一个地方必须调整：如果你用的是普通char数组做偏移表，中文每个汉字是3个字节，最高字节通常大于127。在char默认有符号的编译器上，直接用text[i + m]做索引会变成负数。解决方式前面代码里已经体现了——强制转换成unsigned char。只要转换了，UTF-8文本按字节匹配是没问题的。
如果你的字符串不是单字节编码，而是UTF-16或者按Unicode码点处理，那么更稳妥的做法是先将字符串转成std::u32string，把每个码点当成一个“字符”来处理，偏移表用unordered_map<char32_t, int>而不是固定数组。代价是内存占用变大、哈希查找比数组慢，好处是语义清晰，不会出现按字节处理时的各种边界疑惑。
4. 实测对比：Sunday、Horspool、KMP的真实差距
4.1 它们和Sunday的差别到底在哪里
在工程上做选择之前，先要明白几个容易混淆的算法各自的侧重点：
| 算法 | 核心思想 | 预处理复杂度 | 匹配阶段 | 最坏情况 | 代码复杂度 |
|---|---|---|---|---|---|
| KMP | 利用模式串前缀后缀信息 | O(m) | 主串i不回退 | O(n) | 中 |
| BM | 坏字符 + 好后缀 | O(m + σ) | 尽量多跳 | O(n*m) | 高 |
| Horspool | 只用坏字符，看窗口末尾 | O(m + σ) | 尽量多跳 | O(n*m) | 低 |
| Sunday | 坏字符，看窗口末尾下一个 | O(m + σ) | 尽量多跳 | O(n*m) | 低 |
Horspool和Sunday长得特别像，容易搞混。差别在于失配时看的那个字符：Horspool看的是主串中当前窗口的最后一个字符S[i + m - 1]，Sunday看的是窗口外紧邻的下一个字符S[i + m]。Sunday等于比Horspool更前瞻了一位，实在比较中模式串短时，这一位经常能带来更大的跳跃步幅。
4.2 三组场景下的实测趋势
我在一台CPU比较普通的开发机上，用同一份约5MB的纯文本，分别测了Sunday、Horspool和KMP在不同模式串下的表现。结果不是精确基准，但趋势很稳定：
第一组，模式串为7字节的短关键字，比如"timeout"这种。Sunday和Horspool都明显快于朴素匹配，Sunday比Horspool能再快10%~20%左右，原因是短模式下窗口外字符的命中率更低，Sunday更容易触发m + 1的大跳跃。KMP在短模式串下并没有优势，它的next数组构造和逐位比较的常数因子反而拖了后腿。
第二组，模式串长度为50~100字节，比如一段较长的SQL片段或JSON key路径。这时候BM类算法的优势会收窄，Sunday依然表现不错，但KMP的距离明显缩小。原因是模式串越长，坏字符规则带来的跳跃步幅占比越高，但单次匹配的比较成本也在上升，几种算法被拉开差距的能力变小。
第三组，人为构造的退化文本，比如主串全是"A"，模式串是"AAAB"。Sunday在这里会退化成接近朴素算法的表现，因为每次失配后看的都是同一个字符'B'，偏移表里'B'对应的跳跃距离始终是1。KMP靠next数组保证主串不回退，耗时几乎稳定在O(n)，这种场景下KMP就是压倒性优势。
综合来看，我的选型建议是：默认场景、模式串较短、追求代码简洁，用Sunday；担心恶意或退化输入、对最坏情况敏感，选KMP；模式串很长且匹配次数极多，可以考虑BM；如果只是标准库能解决的单次查找，优先用std::string::find，别再自己造轮子。
4.3 什么时候别用Sunday
Sunday尽管平均性能很好，但它有个弱点：偏移表基于字符集，对模式串内字符覆盖度比较敏感。如果模式串里包含了整个字符集的大部分字符，比如模式串是一个随机生成长度达到几百字节的字符串，那么偏移表里大部分位置的默认m + 1会被覆盖成很小的值，跳跃距离会变得很有限。
另外，如果匹配的文本是高度重复的结构化数据，比如基因序列里"ATCG"这种由极少数碱基组成的字符串，模式串反复用同一批字符，Sunday的跳跃优势也会被削弱。这种场景下面，按字符频率做动态编码、或者用基于后缀结构的算法，才是更专业的方案。所以Sunday不是万能的，它只是“通用短文本搜索”里性价比极高的一员。
5. 踩过的坑和还能继续挖的点
5.1 容易被忽略的边界条件
第一次写完Sunday算法，我在自测时漏掉了几个边界场景，都是实际生产环境里才暴露出来的，列出来供参考：
空模式串。模式串长度为0时，理论上任何位置都算匹配。多数实现里直接在入口返回0。我的代码里加了一行if (m == 0) return 0;，但很多人会忽略。
模式串长度大于主串。不处理就直接进循环，i + m很容易越界。我见过有人在偏移表计算好了之后忘了在循环条件里限制i <= n - m，导致访问越界读，调试半天。正确的做法是入口处直接if (n < m) return -1;。
主串刚好匹配到末尾。当i + m == n时，窗口后面已经没有“下一个字符”可看了。这时必须直接返回-1，不能去读text[i + m]。用调试器看越界问题的时候，八成就是漏了这条。
偏移表下标越界。前面说过，char转换成unsigned char再查表，不是为了规范好看，是真的会因为中文和二进制数据导致崩溃。
5.2 我在实际项目里踩过的坑
有一个印象很深的线上问题：某服务把一条日志里的时间戳字段提取出来做统计，上线后偶尔能收到越界崩溃的报错。排查之后发现，问题出在对“匹配失败后看下一个字符”的逻辑没有限制尾部越界，而且模式串是动态配置的，用户某次配置了一个超长模式串，长度逼近日志行长度，边界瞬间被触发。
后来我把所有Sunday匹配入口都做成防御式写法：先判空、再判长度、再进循环。这看起来是三元组的小事，但在动态模式下是保命的基本盘。还有一次是偏移表用了int shift[256]，却被同时用于处理二进制数据，某条数据里带有0xFF这种字节，直接数组越界。从那以后，我用std::vector<int>并且强制unsigned char下标成了习惯。
5.3 还想再快的优化思路
如果你已经跑通基础版，想进一步榨性能，有几个方向可以考虑：
第一，联合使用Horspool和Sunday的策略。失配时先按Horspool看窗口末尾字符S[i + m - 1]，算一次跳跃距离；再看窗口外的S[i + m]，算一次跳跃距离，两者取大。这样能兼顾“窗口内信息”和“窗口外信息”，但代码会复杂一些，适合追求极致性能的场景。
第二，对模式串做“坏字符 + 尾部锚点”的二段式预筛。在文本里先快速定位S[i + m - 1]和目标模式串末尾字符相同的位置，再对这些候选位置调用严格匹配。本质是用更便宜的字符命中做粗筛，减少全文比较的次数。
第三，利用SIMD指令对纯ASCII短串做并行比较。比如用memcmp的内存块比较代替逐字符循环，在模式串较长时收益非常明显。但要注意memcmp在模式串很短时反而有调用开销，需要实测权衡。
这些优化我都分别尝试过，上线之后真正长期用下来的还是最朴素的基础版加一个“非重叠搜索”小改版。优化不是堆得越多越好，关键要看你的实际数据分布，有时候多写两行防御逻辑比多上两个trick更有效。
最后说点我的个人体会。字符串匹配是那种“看着很小，影响面很大”的基础能力。Sunday算法最大的价值不是单次匹配快多少，而是让你在处理大规模文本时不用一遇到性能问题就上复杂的后缀数组或AC自动机。多数业务场景下，一个几百字节的Sunday实现就够用十年。当然，如果哪天模式串集合大到了成百上千个，那就该切换成多模式匹配算法了，那是另一篇文章的事。
