Shift-And 字符类流式匹配

每个亮位都是一句完整的断言 ​

读完 $T[0..j)$ 后，维护不变量：

也就是说，文本末尾长度 $i+1$ 的一段，恰好匹配模式前 $i+1$ 类。初始文本为空，所有非空前缀都不可能匹配，所以 $D=0$ 正确。

读入新符号时，长度大于一的新候选成立，当且仅当旧文本末尾已经匹配短一位的前缀，并且新符号属于当前类。左移完成前一项，按位与完成后一项。长度一的候选不需要旧匹配，故每步先把最低位置一，再由 $M(c)$ 检查第一类。归纳便证明所有位始终正确，最高有效位也就恰好认证完整匹配。

这个过程可以看成NFA理路非确定性有限自动机Nondeterministic finite automaton · NFA以状态集合保留多条候选运行，并在至少一条运行接受时接受输入的有限状态模型。的特殊链式前沿：一个始终活跃的扫描态，每读一个字符都可启动新分支；每个前缀态只向后一态走。状态集被打包成位，合并同态分支不会丢掉将来所需的信息。接受位只报告“此刻结尾匹配”，不设永久接受自环，否则过去出现过一次便会让以后所有位置都误报。

跨字传递仍是同一次转移 ​

设旧字为 $d_0,\dots ,d_{q-1}$。从低位到高位逐字读取旧值，令第一个输入进位 $b_0=1$，随后

$U_r$ 是该字的有效位掩码，末字可以不足 $w$ 位。输出进位必须取自旧 $d_r$，而非已经与字符掩码相交的 $d_r^{\prime }$。一个前缀是否能延长，要由目的位置的类判断；在源字先筛掉它再传递，会改变原来的状态方程。程序先产生移位数组，再与表中各字相交，避免原地覆盖。

字符类与真正的跨字匹配 ​

取字节字母表 $\mathrm{\Sigma }=\{0,\dots ,255\}$，模式写作 a[ab]b[^b]a。第四类允许任何非 b 字节，方括号只是本例的说明记法。参考程序直接接收五个字节集合，不解析正则表达式语法。

令 $w=3$，用两个字保存五位。下表每个方括号都按低字、高字排列；各字内部仍是高位写在左边，第二字的最高显示位是必须为零的填充位。

在文本 aabxaabya 上逐步运行：

第 $4$ 步最能检验实现：旧低字 110 左移时把最高位 $1$ 传入高字，移位结果为 [101,001]，再与 x 的 [000,001] 相交，得到 [000,001]。若两个字各自独立左移，长度四的候选就丢了。

第 $5$ 步的最低位与完整匹配位同时为一：最后那个 a 既结束第一段，也开始第二段。找到匹配后把状态清零，会漏掉边界 $9$ 的重叠出现。报告的起点可以直接用 $j-m$ 得到，因为本算法每类恰消耗一个符号。

“字符类相容”不能冒充字面相等 ​

考虑模式 a[ab] 与文本 aba。第一类和第二类相交，于是一个草率的 KMP 改写可能把长度二模式的失败链接设成一。读完 ab 匹配后，它认为最后一个字符仍匹配首类 a；再读 a，就错误地报告 ba 也是匹配。

错误在于集合相交只说明“存在一个共同字符”，并没有说明刚读到的 b 属于首类。正确端点只有 $2$；这种快捷写法报出 $2,3$。Shift-And 在边界 $2$ 的状态只有长度二那一位，没有长度一那一位，不会合并这两个不同事实。这里否定的是这条替换规则，不是说所有字符类问题都不能使用自动机预处理。

空模式、空类与字节边界 ​

空模式匹配每个边界；程序把初始边界 $0$ 放在 initial_end，feed 只返回新消耗字节产生的边界。因此连续调用空块不会重复报告 $0$。含空类的非空模式则永不完整匹配，这与空模式完全不同。

接口使用 bytes：UTF-8 的一个汉字通常有多个字节，端点是字节偏移，不是显示字符编号。要按 Unicode 码点或字素簇匹配，必须先给出分词与编码协议，再重建掩码表；本页不隐含归一化、忽略大小写或跨编码等价。

设字母表大小为 $\sigma$，显式类描述的总长度为 $K$，包括重复列出的成员。初始化 $\sigma$ 行、每行 $q$ 个字，再把类成员对应的位设为一，编译时间为

这计入了空类和空模式的输入检查、表头与空行。参考程序不保留原字符类，常驻掩码表和扫描状态共占 $O(\sigma (q+1)+q+1)$ 个字；调用方的原输入另外计算。

非空模式每个文本符号用 $O(q)$ 个字操作，扫描 $n$ 个符号并保存 $z$ 个结果，耗时 $O(nq+z+1)$，额外结果空间 $O(z)$。空模式每步只报告一个边界，耗时 $O(n+1)$。统一可写成 $O(n(q+1)+z+1)$。只有 $m\le w$ 时，非空模式每符号才是常数次字操作。字母表很大时，密集表的 $\sigma q$ 成本也不能消失。

下载实现允许逻辑字宽 $1$ 至 $63$，小字宽专门用于让跨字错误在短例子中暴露；位置计数使用另一个足够宽的整数。模式最多4096位，总消耗字节数不超过 $2^{63}-1$，越界会在消费新块前拒绝。把逻辑字宽设成一，并不声称一位机器字能寻址整个文本。实际复杂度仍按存放计数器、地址和逻辑字的机器字模型解释。

这份前沿适合固定长度字符类的字节流扫描，无须保存已经读过的文本。改变的是被允许的符号表，不是匹配转移；补类与单字符通配符因此不增加每字节的扫描轮数。若输出要求变成插入、删除、替换下的最小费用，就需要不同的状态语义，不能给这些亮位直接加上一个“允许误差”解释。

完整参考程序逐位比较所有活跃前缀，而非只比较最终是否命中；可复核结果包含掩码和完整示例轨迹。六项终点任务要求同时交出端点、跨字状态与错误实现的反例。