Boyer-Moore(BM)算法,文本查找,字符串匹配问题

KMP算法的时间复杂度是O(m + n),而Boyer-Moore算法的时间复杂度是O(n/m)。文本查找中“ctrl + f”一般就是采用的BM算法。
Boyer-Moore算法的关键点:
从右遍历,如果有txt里面的i+j元素和pat里面的j元素不一致,调整。根据right[]调整,right[]类似与KMP算法里面的nextval。skip = j - right[txt.charat(i+j)]; if(skip < 1) skip = 1;  i+=skip; 即找txt里面的第i+j个元素在pat里面的最右边的位置是哪儿,如果存在,两个对齐。如果不存在,直接将i后移到i+j+1的位置。代码如下:
class Solution {
public:
bool search(string pat, string txt) {
//字符串匹配问题,使用BM算法 //计算跳跃表
//-----------------------------------------------
//2^8,一个字符只占一个字节,共8位
int* right = new int[SIZE]; //初始化所有值为-1
for(int i = ; i < SIZE; i++){
right[i] = -;
} //包含在pat模式串中的值为它在其中出现的最右值
for(int i = ; i < pat.size(); i++){
right[pat[i]] = i;
}
//-----------------------------------------------
//在txt中查找字符串pat
int N = txt.size();
int M = pat.size();
int skip = ;
for(int i = ; i <= N - M; i += skip){
//模式串和文本在位置i匹配么?
//匹配失败时,通过跳跃将文本中的字符和它在模式字符串
//出现的最右位置对齐
skip = ;
for(int j = M - ; j >= ; j--){
if(txt[i + j] != pat[j]){
skip = j - right[txt[i + j]];
if(skip < ) skip = ;
break;
}
}
if(skip == ) {
delete[] right;
return true; //或者return i; 找到匹配
}
} delete[] right;
return false; //未找到匹配
}
private:
const int SIZE = ;
};
上一篇:模拟---LCR


下一篇:快速字符串匹配一: 看毛片算法(KMP)