日志关键词筛选那件事我又双叒叕卡住了。服务跑着跑着要在一份几十万行的文本里快速定位某几个关键字最初图省事直接用了朴素逐位匹配结果数据量一上来肉眼可见地慢。旁边同事随口说了一句“字符串匹配你试试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长度m6默认偏移为7。字符位置k偏移m-ks06e15a24r33c42h51然后开始匹配。第一次对齐i0拿S[0..5]substr去比search。第1位s对s第2位u对e失配。看S[06]S[6]ii不在偏移表里使用默认偏移7i跳到7。第二次对齐i7拿S[7..12]ng sea去比search。第1位n对s失配。看S[76]S[13]r查偏移表r的偏移是3i跳到10。第三次对齐i10S[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_castint(text.size()); int m static_castint(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_castunsigned char(text[i m])]; } return -1; } private: void buildShiftTable() { shift_.assign(256, static_castint(pattern_.size()) 1); int m static_castint(pattern_.size()); for (int k 0; k m; k) { shift_[static_castunsigned char(pattern_[k])] m - k; } } std::string pattern_; std::vectorint shift_; };几个注意点shift_.assign(256, m 1)把默认值设成了m 1。这样任何没在模式串里出现过的字符查表直接跳m 1格。遍历模式串时后面的字符会覆盖前面同字符的偏移值天然实现了“最后一次出现位置”的需求。内层比较用text[i j] pattern_[j]这里不要放任何额外逻辑这一层就是纯粹的CPU密集型比较越简洁越好。3.2 找所有匹配重叠与非重叠的处理差异很多场景需要的不只是第一次出现而是所有出现位置。最简单的做法是找到一次匹配后把i加1继续找。这样做能保证不漏掉任何位置包括重叠的匹配。但如果你确认不需要重叠结果可以做得更激进匹配成功后不看匹配窗口内部而是直接查看窗口末尾的下一个字符所在的偏移一次性跳过去。std::vectorint searchAll(const std::string text) const { std::vectorint result; int n static_castint(text.size()); int m static_castint(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_castunsigned char(text[i m])]; } else { if (i m n) break; i shift_[static_castunsigned 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_mapchar32_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 什么时候别用SundaySunday尽管平均性能很好但它有个弱点偏移表基于字符集对模式串内字符覆盖度比较敏感。如果模式串里包含了整个字符集的大部分字符比如模式串是一个随机生成长度达到几百字节的字符串那么偏移表里大部分位置的默认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::vectorint并且强制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实现就够用十年。当然如果哪天模式串集合大到了成百上千个那就该切换成多模式匹配算法了那是另一篇文章的事。