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

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

参考

《柔性字符串匹配》

This post is licensed under CC BY 4.0 by the author.
Contents