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

参考

《柔性字符串匹配》

发表评论

电子邮件地址不会被公开。 必填项已用*标注