字符串匹配算法_多字符串匹配

1. BM（Boyer-Moore）算法

思想：有模式串中不存在的字符，那么肯定不匹配，往后多移动几位，提高效率
BM原理：坏字符规则，好后缀规则

1.1 坏字符规则

在这里插入图片描述

利用坏字符规则，BM算法在最好情况下的时间复杂度非常低，是O（n/m）。比如，主串是aaabaaabaaabaaab，模式串是aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM算法非常高效。
单纯使用坏字符规则还是不够的。因为根据 si-xi计算出来的移动位数，有可能是负数，比如主串是aaaaaaaaaaaaaaaa，模式串是baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM算法还需要用到“好后缀规则”。

1.2 好后缀规则

在这里插入图片描述
从好后缀的后缀子串中，找一个最长的且和模式串的前缀子串匹配的 {v}，滑动至 {v} 对齐

1.3 两种规则如何选择

分别计算好后缀和坏字符规则往后滑动的位数，取大的，作为滑动位数（还可以避免负数）

2. BM算法代码实现

2.1 坏字符

找到坏字符在模式串中的位置有重复的，则是靠后的那个)
采用哈希，而不是遍历。

#define SIZE 256 //字符集字符数
void generateBadCharchar *b, int m, int *badchar)//模式串字符b，模式串长度m，模式串的哈希表)
{ 
   
    int i, ascii;
    fori = 0; i < SIZE; ++i)
    { 
   
        badchar[i] = -1;//哈希表初始化为-1
    }
    fori = 0; i < m; ++i)
    { 
   
        ascii = intb[i]);  //计算字符的ASCII值
        badchar[ascii] = i;//重复字符被覆盖，记录的是最后出现的该字符的位置
    }
}

在这里插入图片描述

int str_bmchar *a, int n, char *b, int m)
//只考虑坏字符方法的程序框架
{ 
   
    int *badchar = new int [SIZE];//记录模式串中每个字符最后出现的位置
    generateBadCharb,m,hash);     //构建坏字符哈希表
    int i = 0, j;
    whilei < n-m+1)
    { 
   
        forj = m -1; j >= 0; --j)  //模式串从后往前匹配
        { 
   
            ifa[i+j] != b[j])
                break;  //坏字符对应模式串中的下标是j
        }
        ifj < 0)   //匹配成功
        { 
   
            return i;   //返回主串与模式串第一个匹配的字符的位置
        }
        //这里等同于将模式串往后滑动 j-badchar[inta[i+j])] 位
        i = i + j - badchar[inta[i+j])]);
    }
    return -1;
}

2.2 好后缀

在模式串中，查找跟好后缀匹配的另一个子串
在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串

不考虑效率的话，上面两个操作都可以暴力查找；
解决办法： 预先对模式串进行处理。
在这里插入图片描述

实现过程：

预处理模式串，填充suffix，prefix

void generateGSchar *b, int m, int *suffix, bool *prefix)
//预处理模式串，填充suffix，prefix
{ 
   
    int i, j, k;
    fori = 0; i < m; ++i)//两个数组初始化
    { 
   
        suffix[i] = -1;
        prefix[i] = false;
    }
    fori = 0; i < m-1; ++i)//b[0,i]
    { 
   
        j = i;
        k = 0;//公共后缀子串长度模式串尾部取k个出来，分别比较)
        whilej >= 0 && b[j] == b[m-1-k])//与b[0,m-1]求公共后缀子串
        { 
   
            --j;
            ++k;
            suffix[k] = j+1;
            //相同后缀子串长度为k时，该子串在b[0,i]中的起始下标
            // 如果有多个相同长度的子串，被赋值覆盖，存较大的)
        }
        ifj == -1)//查找到模式串的头部了
            prefix[k] = true;//如果公共后缀子串也是模式串的前缀子串
    }
}

计算滑动位数

case1：
case2：
case3：（以上都不成立，移动整个模式串（长度m））

2.3 完整代码

/** * @description: 字符匹配BM算法 * @author: michael ming * @date: 2019/6/18 22:19 * @modified by: */
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
#define SIZE 256 //字符集字符数
void generateBadCharchar *b, int m, int *badchar)//模式串字符b，模式串长度m，模式串的哈希表)
{ 

int i, ascii;
fori = 0; i < SIZE; ++i)
{ 

badchar[i] = -1;//哈希表初始化为-1
}
fori = 0; i < m; ++i)
{ 

ascii = intb[i]);  //计算字符的ASCII值
badchar[ascii] = i;//重复字符被覆盖，记录的是最后出现的该字符的位置
}
}
void generateGSchar *b, int m, int *suffix, bool *prefix)//预处理模式串，填充suffix，prefix
{ 

int i, j, k;
fori = 0; i < m; ++i)//两个数组初始化
{ 

suffix[i] = -1;
prefix[i] = false;
}
fori = 0; i < m-1; ++i)//b[0,i]
{ 

j = i;
k = 0;//公共后缀子串长度模式串尾部取k个出来，分别比较)
whilej >= 0 && b[j] == b[m-1-k])//与b[0,m-1]求公共后缀子串
{ 

--j;
++k;
suffix[k] = j+1;
//相同后缀子串长度为k时，该子串在b[0,i]中的起始下标
// 如果有多个相同长度的子串，被赋值覆盖，存较大的)
}
ifj == -1)//查找到模式串的头部了
prefix[k] = true;//如果公共后缀子串也是模式串的前缀子串
}
}
int moveByGSint j, int m, int *suffix, bool *prefix)//传入的j是坏字符对应的模式串中的字符下标
{ 

int k = m - 1 - j;//好后缀长度
ifsuffix[k] != -1)//case1，找到跟好后缀一样的模式子串（多个的话，存的靠后的那个（子串起始下标））
return j - suffix[k] + 1;
forint r = j + 2; r < m; ++r)//case2
{ 

ifprefix[m-r] == true)//m-r是好后缀的子串的长度，如果这个好后缀的子串是模式串的前缀子串
return r;//在上面没有找到相同的好后缀下，移动r位，对齐前缀到好后缀
}
return m;//case3,都没有匹配的，移动m位（模式串长度）
}
int str_bmchar *a, int n, char *b, int m)//a表示主串，长n; b表示模式串,长m
{ 

int *badchar = new int [SIZE];//记录模式串中每个字符最后出现的位置
generateBadCharb,m,badchar);     //构建坏字符哈希表
int *suffix = new int [m];
bool *prefix = new bool [m];
generateGSb, m, suffix, prefix);   //预处理模式串，填充suffix，prefix
int i = 0, j, moveLen1, moveLen2;//j表示主串与模式串匹配的第一个字符
whilei < n-m+1)
{ 

forj = m -1; j >= 0; --j)  //模式串从后往前匹配
{ 

ifa[i+j] != b[j])
break;  //坏字符对应模式串中的下标是j
}
ifj < 0)   //匹配成功
{ 

delete [] badchar;
delete [] suffix;
delete [] prefix;
return i;   //返回主串与模式串第一个匹配的字符的位置
}
//这里等同于将模式串往后滑动 j-badchar[inta[i+j])] 位
moveLen1 = j - badchar[inta[i+j])];//按照坏字符规则移动距离
moveLen2 = 0;
ifj < m-1)//如果有好后缀的话
{ 

moveLen2 = moveByGSj,m,suffix,prefix);//按照好后缀规则移动距离
}
i = i + maxmoveLen1,moveLen2);//取大的移动
}
delete [] badchar;
delete [] suffix;
delete [] prefix;
return -1;
}
int main)
{ 

string a = "abcacabcbcbacabc", b = "cbacabc";
cout << a << "中第一次出现" << b << "的位置从0开始)是：" << str_bm&a[0],a.size),&b[0],b.size));
return 0;
}

在这里插入图片描述

2.4 调试

为方便调试，将字符集SIZE改为3，ascii = intb[i]-'a')

坏字符在模式串中的位置（靠后的那个）
badchar[0]：a是4
badchar[1]：b是5
badchar[2]：c是6
预处理模式串
按规则移动

3. 总结

BM算法的内存消耗
整个算法用到了额外的3个数组，其中bc数组的大小跟字符集大小有关，suffix数组和prefix数组的大小跟模式串长度m有关。
如果处理字符集很大的字符串匹配问题，badchar数组对内存的消耗就会比较多。
因为好后缀和坏字符规则是独立的，如果运行的环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则，就可以避免badchar数组过多的内存消耗。不过，单纯使用好后缀规则的BM算法效率就会下降一些了。
时间复杂度
以上BM算法是个初级版本。这个版本，在极端情况下，预处理计算suffix数组、prefix数组的性能会比较差。
比如模式串是aaaaaaa这种包含很多重复的字符的模式串，预处理的时间复杂度就是O（m^2）。如何优化这种极端情况下的时间复杂度退化，以后再找空研究。
实际上，BM算法的时间复杂度分析起来是非常复杂，论文“A new proof of the linearity of the Boyer-Moore string searching algorithm”证明了在最坏情况下，BM算法的比较次数上限是5n。论文“Tight bounds on the complexity of the Boyer-
Moore string matching algorithm”证明了在最坏情况下，BM算法的比较次数上限是3n。

BM算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率。
BM算法构建的规则有两类，坏字符规则和好后缀规则。
好后缀规则可以独立于坏字符规则使用。
因为坏字符规则的实现比较耗内存，为了节省内存，我们可以只用好后缀规则来实现BM算法。

字符串匹配算法_多字符串匹配

1. BM（Boyer-Moore）算法

1.1 坏字符规则

1.2 好后缀规则

1.3 两种规则如何选择

2. BM算法代码实现

2.1 坏字符

2.2 好后缀

2.3 完整代码

2.4 调试

3. 总结

Published by

风君子

发表回复取消回复

1. BM（Boyer-Moore）算法

1.1 坏字符规则

1.2 好后缀规则

1.3 两种规则如何选择

2. BM算法代码实现

2.1 坏字符

2.2 好后缀

2.3 完整代码

2.4 调试

3. 总结

Published by

风君子

发表回复 取消回复

发表回复取消回复