Shift-and 字符串匹配

wgyhm

2022-11-18

基于位运算的字符串匹配算法。

我们令模式串为 $s$，长度为 $n$ ，文本串为 $t$ ，长度为 $m$ 。字符集大小为 $k$

无特殊说明时，字符串从 $0$ 位开始。

顾名思义，预处理在模式串中进行。而最终计算在文本串内进行。

预处理中，$B_{i,j}$ 表示字符在 $s$ 的第 $j$ 位是否为 $i$。

令 $P$ 表示文本串的匹配情况，$i$ 表示当前枚举到文本串的第 $i$ 位，$P_j$ 表示 $t$ 中 $[i-j,i]$ 与 $s$ 中 $[0,j]$ 是否相等。

考虑从 $i-1$ 到 $i$ 时转移 $P$，P=(P<<1|1)&B[s[i]]

根据定义，这是显然正确的。

我们发现这些操作都与二进制的位操作，所以可以用 bitset 优化。

复杂度预处理 $O(\dfrac{nk}{w})$，主算法 $O(\dfrac{mn}{w})$

主要适用于 $k$ 比较小，且模式串长度也不长的情况。

同样的，预处理在文本串内进行，主算法在模式串中进行。

预处理中，$B_{i,j}$ 表示字符在 $t$ 中的第 $j$ 位为是否为 $i$。

令 $P$ 表示文本串的匹配情况，$i$ 表示当前枚举到模式串的第 $i$ 位，$P_j$ 表示 $s$ 中 $[j-i,j]$ 和 $t$ 中 $[0,i]$ 是否相等。

考虑从 $i-1$ 到 $i$ 时转移，P=(P<<1)&B[s[i]]

$P$ 一开始的 $[0,m-n]$ 位为 $1$。

主算法的复杂度同样也为 $O(\dfrac{mn}{w})$。

考虑到一般情况下文本串的大小大于模式串。主要适用于字符集数量比较小，文本串的动态变化的情况。

解决了 KMP 不能解决的情况，

bzoj2628

动态维护 $B$ 数组。