在 π 的小数位里找一串数字这事听起来像极客式的无聊消遣但它是我见过最适合练手KMP 算法的项目之一。你随便给一个数字串——生日、工号、某个纪念日的日期——然后问它在 π 的小数位里第几位出现如果找不到那至少要扫到多少位才敢说“没找到”这个“查找”动作看似简单背后却把字符串匹配的最坏情况、大数运算的精度控制、流式处理的边界处理全串起来了。我把这个项目从零跑了一遍中间踩了不少坑尤其是索引差一、保护位不够、分块重叠区重复计数这几类问题几乎每个都让我重跑了一次千万位数。这篇就把整套思路、源码和排查经验摊开讲适合刚学完 KMP 想找个真实场景落地的同学也适合想了解大数计算怎么和字符串算法配合的开发者。1. 先把项目拆开到底要解决什么问题标题里塞了两件东西KMP 算法和圆周率的小数位。表面看是硬凑实际拆开之后你会发现这是一个非常干净的“输入-预处理-匹配-验证”四段式工程每一段都有明确的取舍空间。1.1 从一个双关梗说起π 数组和圆周率先说个很多人不知道的命名巧合。KMP 算法里那个用来记录“最长相等前后缀长度”的数组在大量教材和论文里被写成π 数组pi array因为希腊字母 π 在数学里常用来表示一种映射关系。而我们要搜的目标恰好就是圆周率 π 的十进制展开。两个 π一个是抽象的前缀函数表一个是 3.14159 后面那串无穷无尽的数字名字撞车但性质完全不同。这个巧合其实挺有用。它逼着你在写代码时给变量起清晰的名字否则pi到底指哪个三天后自己都看不懂。我在第一版里就犯过这个错函数build_pi(p)返回的是前缀函数表旁边又有个变量pi_str存圆周率文本读到第三遍才反应过来。后来统一改成prefix_table和pi_digits代码立刻清爽。拆解需求的话这个项目其实包含三个独立子问题第一怎么产生任意长度的 π 小数位第二怎么在生成的数字流里高效查找一个模式串第三怎么验证找到的位置是对的。第三个最容易被忽略但恰恰是最关键的——你搜出来一个位置凭什么相信它没有独立验证手段整个项目就是自娱自乐。1.2 三条实现路线与选型理由在动手前我认真比过三条路线这里把取舍逻辑写清楚因为选型决定了后面 80% 的工作量。路线 A先算 π落地成文件再用 KMP 扫文件。这是最笨但最稳的做法。优点是算和搜彻底解耦π 文件可以复用调试 KMP 时不用每次重算。缺点是磁盘占用1 亿位纯数字就是 100MB 左右加上换行分组会再多一点。我最终选的就是这条理由很实际调试期最怕耦合KMP 写错的时候你根本不知道是算法错了还是 π 算错了。路线 B边算边搜算一位搜一位。听起来优雅实际上很别扭。π 的 spigot 类算法是逐位吐数字的但吐出来的位必须先凑够模式长度才能开始比对而且一旦发现不匹配要回退回退的位已经被丢掉了。要在流上做 KMP你得自己维护一个长度等于模式串的滑动窗口缓冲区本质还是路线 A 的内存版。除非你算到百亿位、磁盘放不下否则没必要。路线 C不自己算直接用现成的位数文本。这不算偷懒做算法实验时非常合理。π 的位数文本是公开资源抓一份现成的比你自己写大数运算靠谱得多。我的建议是第一次跑通验证用现成文本确认 KMP 没问题后再换成自己算的对比两者在同一段前缀上是否完全一致。这一步交叉验证能同时抓住两边的 bug。提示如果你只是想验证 KMP 的正确性完全不需要真 π。随便造一段长随机数字串就行。真 π 的价值在于它是一个“公认的、可外部核对的”标准答案能帮你排除“算法和测试数据一起错”的尴尬。2. KMP 的核心原理与手工推演这一段我不打算复述教科书。网上讲 KMP 的文章多如牛毛但大部分卡在同一个地方告诉你 next 数组怎么求却没讲清楚为什么这样求出来的东西能让文本指针不回退。我用自己的理解方式重讲一遍配合手推过程。2.1 前缀函数到底在记录什么定义一句话对模式串pprefix_table[i]表示子串p[0..i]的最长相等真前缀与真后缀的长度。“真”是指不能是整个串本身。举个例子p ababacap[0..0] a没有真前后缀长度 0p[0..1] ab前缀 a 后缀 b不等0p[0..2] aba前缀 a 后缀 a长度 1p[0..3] abab前缀 ab 后缀 ab长度 2p[0..4] ababa前缀 aba 后缀 aba长度 3p[0..5] ababac0p[0..6] ababaca前缀 a 后缀 a长度 1所以表是[0, 0, 1, 2, 3, 0, 1]。这个表为什么有用想象你在文本里已经成功匹配了模式的前 5 个字符ababa第 6 个字符对不上。朴素做法是把模式整体右移一位从b重新开始比等于把已经确认过的信息全扔了。但你知道ababa的后缀aba和它的前缀aba是一样的所以模式可以直接滑到让前缀aba对上刚才那三个字符的位置从第 4 个字符继续比。前缀函数就是这个“能滑多远”的量化答案。我个人的类比是这就像你背一串很长的密码背到第 6 位发现错了但你不会从头重背而是回想“刚才中间有一段我确认过是对的”从那一段的末尾接着往下。KMP 做的事就是把这种“回想”变成确定的、可计算的规则。2.2 手推一个例子把每一步摊开光看定义还是会晕我用p aabaaab手推一遍构造过程这是我自己理解透的那一次。构造时用双指针i从 1 开始遍历模式串k记录当前已匹配的前缀长度初值 0。p a a b a a a b i 1: p[1]a, p[0]a, 相等 - k1, table[1]1 i 2: p[2]b, p[1]a, 不等 - k 回退到 table[0]0 p[2]b, p[0]a, 仍不等 - table[2]0 i 3: p[3]a, p[0]a, 相等 - k1, table[3]1 i 4: p[4]a, p[1]a, 相等 - k2, table[4]2 i 5: p[5]a, p[2]b, 不等 - k 回退到 table[1]1 p[5]a, p[1]a, 相等 - k2, table[5]2 i 6: p[6]b, p[2]b, 相等 - k3, table[6]3结果是[0, 1, 0, 1, 2, 2, 3]。这里有个特别容易忽略的细节k回退的时候用的是table[k-1]而不是table[k]。为什么因为k表示“我已经匹配了 k 个字符”当第 k 个字符对不上时下标是k我要找的是前k个字符p[0..k-1]的最长相等前后缀那正好是table[k-1]。这个下标在写代码时错一个就全乱我见过太多人在这里翻车包括我自己。2.3 匹配阶段为什么文本指针永不回退匹配阶段的结构和构造阶段几乎一模一样区别只在于一个扫模式串、一个扫文本串。核心循环长这样k 0 for i, ch in enumerate(text): while k and ch ! pat[k]: k prefix_table[k - 1] if ch pat[k]: k 1 if k m: # 找到一次匹配起点是 i - m 1 k prefix_table[k - 1]关键在于那个for i, ch in enumerate(text)。i是单调递增的永远不回头。每一次失配减少的只是k也就是“已经匹配了多少个模式字符”。文本的读取位置和模式的匹配长度是两个互相独立的量这是 KMP 最反直觉也最优美的地方。为什么总能这样因为当你在i处失配时你已经确认了文本里text[i-k..i-1]这 k 个字符等于模式的前 k 个字符。前缀函数告诉你这 k 个字符里有一段长度t的后缀等于模式的前t个字符。于是你不需要看文本就可以断定text[i-t..i-1]已经和模式前 t 个字符匹配上了直接从k t开始继续比。信息没有丢失只是被压缩成了k这一个整数。注意找到一次完整匹配后不要直接把k重置为 0而要重置为prefix_table[m-1]。否则像aaaa里找aa本来有 3 处匹配你会只找到 1 处。这是统计出现次数时的经典错误。2.4 和朴素匹配、Rabin-Karp、内置 find 的正面对比我一直觉得判断一个人是否真懂 KMP看他能不能说出“什么时候不该用 KMP”。下面这张表是我的实际体感总结方案时间复杂度最坏情况实现复杂度适用场景朴素双循环O(n×m)极端退化极低短文本、模式极短KMPO(nm)稳定线性中长文本、需要稳定最坏界Rabin-Karp期望 O(nm)O(n×m) 可构造中多模式、需要哈希复用语言内置 find视实现多为线性稳定极低只用结果、不管过程朴素匹配在 π 上表现其实不差因为 π 的数字分布接近均匀随机一旦失配通常第一个字符就对不上平均比较次数接近常数。真要让它退化得构造aaaa...a这种高度重复的文本加aaab这种模式。π 里不会出现这种情况所以如果你的目标只是“在 π 里找到某个串”用内置find最快最省事这点我后面还会强调。但写 KMP 的价值不在跑分在于三件事可控你知道每一步在干什么、可移植换语言、换嵌入式环境照样能用、可扩展改成多模式匹配、改成流式扫描都很自然。这个项目练的就是这三样。Rabin-Karp 值得单独提一句因为它在这个场景下其实挺合适滚动哈希常数小实现简单而且模式长度固定时只需要一次预处理。它的风险是哈希碰撞需要双模数兜底而 KMP 没有这个问题——要么匹配要么不匹配不存在“概率性正确”。做验证类工作我更信任确定性算法。3. π 小数位的生成与文本化这一节是整个项目里最容易被低估的部分。很多人以为“算 π 有什么难的一行公式”实际写下去会发现整数除法截断、保护位不足、大数除法性能这三座山一个都绕不过去。3.1 Machin 公式的整数化改造我选的是 Machin 类公式π/4 4·arctan(1/5) − arctan(1/239)选它的理由很直接收敛快只需要两个 arctan 展开实现短几十行代码就能跑而且全程可以用整数运算搞定不碰浮点。浮点在千万位级别早就崩了double 才 15 到 17 位有效数字后面全是噪声。整数化的思路是这样的设定一个“单位”one 10^(Nguard)把所有量都放大one倍用大整数表示。arctan(1/x)的级数展开是arctan(1/x) 1/x − 1/(3x³) 1/(5x⁵) − 1/(7x⁷) ...每一项单独用整数除法算除以(2k1)时丢掉的小数部分远小于最后一个保护位只要 guard 留够就无所谓。核心函数这么写def arctan_inv(x, one): 返回 arctan(1/x) * one 的整数近似值 x2 x * x term one // x # 第一项 1/x total term n 1 sign -1 while term: term // x2 # 每轮多乘一个 1/x² total sign * (term // (2 * n 1)) sign -sign n 1 return total def pi_scaled(digits, guard20): one 10 ** (digits guard) val 4 * (4 * arctan_inv(5, one) - arctan_inv(239, one)) return val # 等于 π * 10^(digitsguard)while term:这个终止条件很关键。因为整数除法向下取整当term缩到 0 时后面所有项都贡献不了非零值自然可以停。这比预先算项数更稳不会因为估算偏差少算几项。拿到val之后转成字符串整数位是第一位必然是 3后面就是小数位s str(pi_scaled(N)) assert s[0] 3 frac s[1:1 N] # 前 N 位小数assert s[0] 3这个断言不是仪式感它是你唯一能低成本发现“保护位不够”的手段。保护位不够时误差会往高位传播最先污染的就是末尾严重时连整数位都会变。跑一次断言比对着结果一个个数快得多。3.2 项数估算与保护位该怎么定guard 到底留多少这不是拍脑袋可以算。要保证第 N 位小数准确误差必须小于 10^-(N1) 量级。级数第 k 项的量级是1/((2k1)·x^(2k1))要求它小于 10^-N(2k1)·log10(x) N k ≈ N / (2·log10(x))代入两个 xx 5log10(5) ≈ 0.69897k ≈ N / 1.398也就是每 1.4 位小数需要多算一项x 239log10(239) ≈ 2.3784k ≈ N / 4.757每 4.76 位一项所以算 10 万位小数arctan(1/5)那一支要循环约 7.15 万次arctan(1/239)那一支只要约 2.1 万次。前者是瓶颈这也解释了为什么选更小的 x比如 1/5能加速收敛——但 x 太小级数项数反而增加得权衡。用 1/5 和 1/239 这组是历史上验证过的甜蜜点。guard 的取值我的经验是20 位起步。理由是末尾几项的有效贡献不到 1 个单位累计误差大约在几个单位量级20 位十进制约 66 比特的余量足够吸收。跑到 10^7 位时我把 guard 提到 30纯粹是心理安慰实际上 20 也够。真正的风险不在 guard在后面。3.3 输出、校验与分块写入大整数转字符串这一步Python 在 3.11 之后对超大整数转十进制字符串加了位数限制默认 4300 位跑百万位会直接抛ValueError。处理办法是调用sys.set_int_max_str_digits(0)关掉限制或者用decimal模块。我踩过这个坑报错信息还挺隐晦第一次遇到时以为是内存问题。写文件时不要一次性write一个巨大字符串分块写更友好也方便加进度。我的做法是按每 10000 位一段往文件里追加同时维护一个全局位置计数器。这里有个小设计文件里只存纯数字不加换行、不加空格。原因很简单任何格式字符都会让“第 N 位”和“文件偏移第 N 字节”对不上后面排查位置差一会让你怀疑人生。如果你确实需要换行方便人眼阅读那就在读取时先过滤掉非数字字符但要记得位置计数不能用字节偏移必须用过滤后的逻辑下标。校验环节我用了两个手段。第一比对已知前缀π 的前 100 位小数是公开的固定串自己算出来的前 100 位必须一模一样否则立刻停。第二比对末位稳定性用 guard20 和 guard30 各算一次前 N 位应该完全相同如果末几位有差异说明 guard 不够或者项数截断有问题。这两个检查加起来不到二十行代码能省掉后面几小时的困惑。4. 完整实操从零跑通全流程前面都是铺垫这一节把整个流程串起来给出可以直接抄的代码和实测记录。我按实际操作顺序写包括我调整参数的过程。4.1 环境与目录规划环境没什么特殊要求Python 3.9 以上就够不需要第三方库。目录我这么分的pi-kmp/ ├── gen_pi.py # 生成 π 小数位并落盘 ├── kmp.py # KMP 核心前缀表构建 单串匹配 流式扫描 ├── bench.py # 基准测试与对比 ├── data/ │ └── pi_1e6.txt # 100 万位纯数字 └── out/ └── hits.txt # 命中位置记录这个划分的意义在于kmp.py完全不依赖gen_pi.py。你可以拿kmp.py去搜任何文本π 只是它处理的一个输入。这种解耦在调试阶段价值巨大我前面强调过了。生成脚本的关键参数只有三个目标位数N、保护位guard、输出路径。我的默认组合是N1000000, guard20。4.2 核心代码KMP 分块流式扫描先给前缀表构建和基础匹配这两个函数是所有功能的基石def build_prefix_table(pat): m len(pat) table [0] * m k 0 for i in range(1, m): while k and pat[i] ! pat[k]: k table[k - 1] if pat[i] pat[k]: k 1 table[i] k return table def kmp_find(text, pat, tableNone): 返回所有匹配起点0-based if not pat: return [] table table or build_prefix_table(pat) m len(pat) k 0 hits [] for i, ch in enumerate(text): while k and ch ! pat[k]: k table[k - 1] if ch pat[k]: k 1 if k m: hits.append(i - m 1) k table[k - 1] return hits然后是分块扫描。这段是真正有技术含量的部分也是最容易写错的地方def kmp_scan_file(path, pat, chunk_size1 20): 流式扫描文件返回命中起点逻辑下标不含任何格式字符 if not pat: return table build_prefix_table(pat) m len(pat) keep m - 1 # 需要保留的重叠长度 k 0 overlap base 0 # 下一个块的 data[0] 之前的全局位置基准 last_hit -1 with open(path, r, encodingascii) as f: while True: buf f.read(chunk_size) if not buf: break data overlap buf start_offset base - len(overlap) # data[0] 的全局下标 for i, ch in enumerate(data): while k and ch ! pat[k]: k table[k - 1] if ch pat[k]: k 1 if k m: pos start_offset i - m 1 if pos last_hit: # 去重重叠区可能重复报告 last_hit pos yield pos k table[k - 1] overlap data[-keep:] if keep else base len(buf)这里有三处必须讲清楚每一处我都曾经写错过第一start_offset的账。data overlap buf而overlap是上一个块末尾的字符它已经在上一轮被计过位置了。所以这一轮data[0]的全局下标是base - len(overlap)不是base。我第一版就是漏了这个减号结果所有跨块边界的命中位置都偏了m-1而块内部的命中完全正确——这种“部分正确”的 bug 最难发现。第二重叠区必须去重。如果一次匹配完全落在overlap内部它上一轮已经被报告过了这一轮会再报一次。用last_hit单调递增过滤最简单前提是扫描是顺序的、命中位置单调递增——KMP 的顺序扫描天然满足。第三keep m - 1不是m。保留m-1个字符就够覆盖所有跨界匹配因为任何长度 m 的匹配最多只有m-1个字符落在上一块里。保留多了浪费内存保留少了会漏匹配。这个数字算错的人不少。C 版本的匹配核心给一份方便需要移植的同学#include vector #include string std::vectorint buildPrefix(const std::string p) { int m p.size(); std::vectorint t(m, 0); int k 0; for (int i 1; i m; i) { while (k 0 p[i] ! p[k]) k t[k - 1]; if (p[i] p[k]) k; t[i] k; } return t; } // 在内存中的文本上查找返回全部起点 std::vectorint kmpFind(const std::string s, const std::string p) { std::vectorint hits; if (p.empty()) return hits; auto t buildPrefix(p); int m p.size(), k 0; for (int i 0; i (int)s.size(); i) { while (k 0 s[i] ! p[k]) k t[k - 1]; if (s[i] p[k]) k; if (k m) { hits.push_back(i - m 1); k t[k - 1]; } } return hits; }C 的整数溢出不用担心只要s.size()不超过int上限。真要处理几十亿位文本记得把索引换成size_t并且分块读时用std::ifstream::read而不是getline。4.3 跑一遍基准用例Feynman point有没有一个公认的、可以外部核对的测试点有。π 的小数位里有一段著名的连续六个 9业界常拿它当基准位置是小数点后第 762 位。这个结论广为流传但我建议你自己跑一遍再信因为索引约定不同很容易差一。用我们的代码验证frac open(data/pi_1e6.txt).read() # 纯小数位不含整数位 3 hits kmp_find(frac, 999999) print(hits[0]) # 输出 761为什么是 761 不是 762因为frac是从小数点后第一位开始编号的0-based 下标 761 对应“第 762 位”。如果你把整数位的3也拼进字符串那结果就是 762。这个差一完全来自编号约定不是 bug。我在项目里专门写了一个注释块说明这件事因为每次重看都要愣一下。验证通过后就可以做更有意思的测试了。我跑过这几个查询模式串说明查找结果处理方式14159265前 8 位应命中下标 0999999Feynman point首次命中下标 761123456789递增序列千万位内未必命中需报“未找到”20240101某个日期结果只作参考无外部答案可核最后一行很重要不是所有查询都有标准答案。对于随机日期这类模式你只能报告“在前 N 位内未找到”或“首次出现在第 X 位”然后靠第二份独立实现交叉验证。我的做法是同时跑 Python 的kmp_find和str.find两者结果必须完全一致否则停下来查。这比盯着代码看有效得多。4.4 性能实测与调参记录数据量级对应的实测感受我给个大致区间。必须说明具体数字和机器强相关下面的时间只作量级参考不要拿来当基准线。生成阶段纯 Python 大整数运算在百万位量级还能接受几十秒到几分钟到千万位就明显吃力主要开销在term // x2这种超大整数除法上位数越大越慢。真要做千万位以上我的建议是换成基于 Chudnovsky 公式加二分拆分的实现或者引入加速大整数运算的第三方库纯 Python 硬扛性价比太低。扫描阶段KMP 扫 100 万位、模式长度 8纯 Python 大概在零点几秒到一两秒扫 1000 万位大概十几秒。相比之下str.find快一个数量级以上因为 CPython 底层是 C 实现的快速搜索算法还做了大量优化。这个差距必须诚实面对如果你只要结果str.find完胜KMP 在这里的价值是教学和可移植性。调参上chunk_size我最后定在 1MB。更小的块比如 64KB会频繁触发文件读和重叠拼接反而慢更大的块比如 16MB对内存不友好而且重叠区去重的收益没变。1MB 是个不错的平衡点块内局部性好读盘次数也合理。还有一个反直觉的发现模式串长度对 KMP 速度的影响远小于预期。模式从 8 位加到 64 位扫描时间增加不到 10%。原因很朴素——前缀表构建是 O(m)但 m 才几十忽略不计匹配阶段的比较次数几乎不变因为 π 的随机性让失配来得很快。只有在高度重复的文本上模式长度才会显著影响性能。5. 踩坑实录与排查速查表这一节是我最想写的部分。前面那些“应该怎么做”搜一搜都能找到下面这些坑得自己踩过才知道疼。5.1 结果对不上时的四层排查法结果不对是常态关键是怎么快速定位。我总结了一个从外到内的四层排查顺序每次按顺序走基本十分钟内能锁定问题。第一层先确认 π 本身对不对。拿前 100 位小数和公开值逐位比对Python 里直接assert。这一步排除大数运算的问题。如果这层就错了问题在 guard、项数或者sys.set_int_max_str_digits先别碰 KMP。第二层确认模式串在答案里的位置。用text.find(pat)在同一份文本上跑一遍和kmp_find的结果比对。两者不同说明 KMP 实现有 bug两者相同但和预期不同说明是文本或者预期值出了问题。这一步的关键是“同一份文本”很多人用不同的数据源比对结果越比越乱。第三层用极小的用例隔离 KMP。构造textabababcab、patababc这种手算得出答案的例子跑前缀表和匹配。如果小例子对、大例子错八成是分块逻辑的锅如果小例子就错去查前缀表的下标。我遇到过if pat[i] pat[k]里把k写成i-1的情况小例子一跑立刻暴露。第四层查分块的边界。构造一个能让匹配跨越块边界的用例把chunk_size设成 4模式设成 5 位让匹配必然跨界。这一步专门抓keep长度不够、start_offset算错、重叠区没去重这三类问题。我建议所有分块代码都必须用极小的 chunk_size 跑一次测试这是最便宜的边界测试。提示把chunk_size调小不只是测试手段也是调试手段。生产跑大块调试跑 4 字节的小块日志一打跨块逻辑对不对一眼就看出来了。5.2 内存、速度与精度三个方向的坑内存坑。把 1 亿位 π 一次性读成字符串Python 的str每个字符对象开销远大于 1 字节实际占用可能是理论值的数倍。正确做法是分块读、流式扫别图省事写read()。我用open(...).read()跑 1000 万位时峰值内存比我估算的高出一大截后来改成流式就好了。另外如果你想用bytearray或者直接读二进制能进一步压缩内存代价是比较时要处理字节和字符的转换。速度坑。生成阶段最大的速度杀手是str(big_int)。超大整数转十进制字符串的复杂度不低位数到千万级时这一步可能比运算本身还慢。如果你的流程里只需要整数比较、不需要字符串那就别转。反过来如果你只需要文本、不需要再做运算那就生成完立刻落盘别在内存里反复转。精度坑。这个最隐蔽。表现是前 N-5 位全对最后几位是乱的。原因可能是 guard 太小、项数截断太早比如用for k in range(K)而不是while term、或者落盘时把末位截断了。我的处理办法是只在有效位数内使用结果算出 Nguard 位但对外声称只保证 N 位最后 guard 位直接丢掉别去核对它。这样即使有微小误差也不会污染结论。还有一个特别隐蔽的坑从文件读出来的字符串可能带\n。如果你为了人眼阅读在文件里每 60 位加一个换行那frac里就混进了\n匹配位置全乱而且匹配本身还是“成功”的只是位置全错。解决办法要么存纯数字要么读入时replace(\n, )并明确记录“位置是逻辑下标”。我建议存纯数字别给自己找麻烦。5.3 常见问题速查表现象最可能原因排查动作所有位置都差m-1分块start_offset漏减len(overlap)用小 chunk 测跨块匹配同一位置被报告多次重叠区未去重加last_hit单调过滤跨界匹配全部漏掉keep取成 0 或小于m-1检查keep m - 1末几位数字乱码guard 不足或项数截断guard 加到 30 重算比对大整数转字符串报错位数限制未解除调用set_int_max_str_digits(0)位置整体偏移文本里混入换行或空格只存纯数字或读入时过滤匹配数少于实际命中后k重置为 0改成k table[m-1]前缀表在小例子上就错k回退用了table[k]改为table[k-1]扫描速度远慢于str.find纯 Python 循环开销属正常现象改用内置或 C 扩展生成千万位卡死大整数除法主导换更快的公式或多进程拆分最后补一个我认为最值钱的技巧给你的实现写一个“自检模式”。开启后它会在小规模数据上把 KMP 结果和内置find结果逐项比对不一致就直接抛异常。这个开关平时关着不影响性能一旦你改了代码逻辑就打开跑一遍。我靠这个习惯避免了至少三次把错误实现带进下一篇实验。我个人在这个项目里最大的体会是算法本身的难度往往不是项目的主要难点。KMP 的代码我两天就写对了剩下的四天全花在索引约定、分块边界、精度控制和交叉验证上。真想把这个项目做扎实把时间预算按三比七分给“算法”和“工程细节”会顺利很多。至于还能怎么玩把单模式换成多模式用前缀表批量搜索一组生日或者把扫描器改成在线模式让它一边生成 π 一边输出命中——这两条路我都试过前者用 Aho-Corasick 收敛更快后者需要自己维护滑动窗口都能在这个代码骨架上直接长出来。