非常简洁的shift-and / shift-or教程

$shift-and$字符串匹配算法适用于模式串长 $|P|$短于机器字长$w$的情况，直接用位运算来$O(|T||P|/w)$获得文本串后缀和模式串前缀的所有匹配信息

定义

文本串$T$，模式串$P$，不解释了

位向量$D$：$D$的长度为$P$的长度，每一位表示前缀的匹配程度，$D[j]=1$表示前缀$P[0,j]$匹配后缀$T[i-j,i]$

预处理位向量数组$B[Σ]$：对于字符集$Σ$的每一个字符$c$，$B[c][j]=1$表示$c$允许在位置$P[j]$出现

过程

还是增量法的观点，假设已经处理好$T[0,i-1]$的状态，现在考虑迭代到$T[i]$的更新

此时对于任意的$j$，更新$D[j]=1$当且仅当$D[j-1]=1$①且$T[i]=P[j]$②

$D[j-1]=1$意味着对于文本串后缀$T[i-j+1,i]$的前缀$T[i-j+1,i-1]$与模式串前缀$P[0,j]$的前缀$P[0,j-1]$相匹配，此时剩下的只需$T[i]=P[j]$

翻译成位运算的更新操作就是：$D = ((D<<1) + 1) \& B[T[i]]$

其中，左移1并加1就是说，加入之前的上一位是匹配的，那当前则认为也是匹配，最低位的前一位是空串，我们也认为匹配（满足①），$B[T[i]]$则检查所有$P$串的位置$i$是否允许存放$T[i]$对应的字符（满足②）

这样我们每一次迭代$T$的位置$i$，都能更新$P$的所有匹配信息

当 $D[|P|-1]=1$时，就是说当前$T$的后缀完全匹配了整个$P$

至于$shift-or$则是把位向量的0和1含义取反，使得更新可以简化为 $D = (D<<1) | B[T[i]]$

完成版

#include<bits/stdc++.h>
using namespace std;
int main() {
    string T = "cbcbcbaefb";
    string P = "cbcba";
    bitset<5> D,B[26];
    for(int j = 0; j < P.length(); j++) {
        B[P[j]-'a'].set(j);
    }
    for(int i = 0; i < T.length(); i++) {
        D = D << 1;
        D.set(0);
        D &= B[T[i]-'a'];
        if(D.test(P.length()-1)) {
            cout << "match@ " << i-P.length()+1 << endl;
        }
    }
    return 0;
} 

参考

《柔性字符串匹配》