非常简洁的 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;
} 

参考

《柔性字符串匹配》