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

定义

文本串TT,模式串PP,不解释了

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

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

过程

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

此时对于任意的jj,更新D[j]=1D[j]=1当且仅当D[j1]=1D[j-1]=1①且T[i]=P[j]T[i]=P[j]

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

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

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

这样我们每一次迭代TT的位置ii,都能更新PP的所有匹配信息

D[P1]=1D[|P|-1]=1时,就是说当前TT的后缀完全匹配了整个PP

至于shiftorshift-or则是把位向量的0和1含义取反,使得更新可以简化为 D=(D<<1)B[T[i]]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;
} 

参考

《柔性字符串匹配》