我最喜欢的字符串匹配算法 Bitap：从暴力法一路推导出的位运算之美

概述

作者想找一个既优雅又好懂的字符串匹配算法，最终锁定适合「模式较短（短于一个机器字长）」场景的 bitap（也称 shift-and）算法。他没有直接抛结论，而是从最朴素的暴力匹配逐步改写：先把「读前看」改成对一堆「进行中的匹配」做流式维护；接着发现这些中间状态本质是 0..len(P) 之间的一堆整数，而状态集合恰好能塞进一个机器字当作位集；最后用两条关键位运算收尾——无条件左移一位推进所有状态，再与按字符预计算的 validMask 做按位与、把无效转移一次性过滤。于是原本的双层循环被压成每个输入字符的一次移位加一次按位与。他也坦诚局限：模式长度受字宽约束、渐进复杂度与暴力法同阶、单次测试甚至可能更慢，但它的可推导性与简洁正是迷人之处。