Bitap：我最爱的字符串匹配算法
Bitap: My favorite string matching algorithm
在字符串匹配领域，Boyer-Moore和Knuth-Morris-Pratt等经典算法广为人知，但Bitap（或称shift-and）算法却常被忽视。这篇文章详细推导了Bitap算法，展示了如何从最朴素的暴力匹配出发，通过引入流式处理思想，最终利用位运算（bit manipulation）将状态集合压缩为单个整数，从而实现对短模式的高效匹配。尽管Bitap在渐近复杂度上与朴素算法相同，且仅在模式较短时优势明显，但我依然钟爱它，因为它的推导过程极其优雅，逻辑清晰，比许多复杂算法更容易从第一性原理推导出来。
尽管我也深入研读过Boyer-Moore和KMP算法，但我需要花费相当长的时间才能从零推导它们，而Bitap却非常容易推导，因为对我来说，它只是换了一种形式的朴素算法。
HN 评论区
10- Rendello
我也有一个最爱的字符串匹配算法，就是这篇由 Wojciech Muła 撰写的文章 [1] 中提到的 "Generic SIMD"（我还没细读另外两个 SIMD 算法，因为我不打算去用 intrinsics）。
那条帖子的评论区 [2] 里也有一些很好的留言，其中包括 ripgrep 作者 burntsushi 的评论。
- MattPalmer1086
啊，上周末我正好在更新自己的字符串搜索算法，当模式长度小于 64 时，改用 Bitap（Shift-OR 变体）替代 KMP。确实更快。这真是一个非常漂亮的算法。
我的搜索算法 HashChain [1] 是一个非常快的亚线性算法，但它使用 KMP（现在也包括 Bitap）来验证匹配，因此最坏情况是线性的（而不是像 Boyer Moore Horspool 那样的二次方）。
- MattPalmer1086
这是从第一性原理推导 Bitap 的绝佳过程。我之前从未见过这样的推导。干得漂亮！
一个小瑕疵：作者说朴素算法是线性的——也许平均情况下是，但它的最坏情况复杂度是二次方的。而 Bitap 即使在最坏情况下也是线性的。