字符串匹配算法适用于模式串长 短于机器字长的情况,直接用位运算来获得文本串后缀和模式串前缀的所有匹配信息
定义
文本串,模式串,不解释了
位向量:的长度为的长度,每一位表示前缀的匹配程度,表示前缀匹配后缀
预处理位向量数组:对于字符集的每一个字符,表示允许在位置出现
过程
还是增量法的观点,假设已经处理好的状态,现在考虑迭代到的更新
此时对于任意的,更新当且仅当①且②
意味着对于文本串后缀的前缀与模式串前缀的前缀相匹配,此时剩下的只需
翻译成位运算的更新操作就是:
其中,左移1并加1就是说,加入之前的上一位是匹配的,那当前则认为也是匹配,最低位的前一位是空串,我们也认为匹配(满足①),则检查所有串的位置是否允许存放对应的字符(满足②)
这样我们每一次迭代的位置,都能更新的所有匹配信息
当 时,就是说当前的后缀完全匹配了整个
至于则是把位向量的0和1含义取反,使得更新可以简化为
完成版
#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;
}
参考
《柔性字符串匹配》