第2章第3节练习题3 串的模式匹配(BM)

时间:2022-02-24 12:28:50

问题描述

设有主串S和子串T,子串T的定位就是要在主串S中找到一个与子串T相等的子串。

算法简述

第2章第3节练习题3 串的模式匹配(BM)中对KMP算法进行了详细分析,本节对BM算法进行扼要分析。

BM算法即Boyer-Moore字符串搜索算法,是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore二人于1977年提出,对子串进行了一次预处理,从而使得子串与主串无需逐次比较。

本节中采用的主串和子串如下:

主串:HERE-IS-A-SIMPLE-EXAMPLE
子串:EXAMPLE

BM算法采用的后缀匹配的思想,即匹配字符串时并不是传统意义上的从左向右进行,而是采用自右向左进行比较。为了更快的比较,BM算法定义了好后缀坏字符两个概念以及两个相关规则:好后缀规则坏字符规则,定义如下:

坏字符:主串与子串从后向前比较时,不相同的字符。
好后缀:主串与子串从后向前比较时,保持连续相同的若干个字符及其包含的右对齐子字符;

用下面的例子简单的介绍下坏字符和好后缀。

主串 A - S I M P L E
子串 E X A M P L E

根据坏字符和好后缀的定义,得到该例中的坏后缀和好字符:

好后缀有: MPLE, PLE, LE, E
坏字符为: A

上面介绍完了坏字符和好后缀的基本定义,下面便对坏字符规则和好后缀规则做一个简单的介绍,并对执行过程进行一次梳理。

坏字符规则: 后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置;
好后缀规则: 后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置。

这里先从整体上简单的梳理下执行过程。

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
S[i] H E R E - I S - A - S I M P L E - E X A M P L E
T E X A M P L E
T E X A M P L E
T E X A M P L E
T E X A M P L E
T E X A M P L E
  • 第一轮比较中,S[6]!=T[6],同时发现S[6]并不在子串T中,根据坏字符规则,即将子串T后移6-(-1)=7位,因为无好后缀,进入第二轮比较;
  • 第二轮比较中,S[13]!=T[6],但发现S[13]在子串T中,根据坏字符规则,将子串T后移6-4=2位,因为无好后缀,进入第三轮比较;
  • 第三轮比较中,S[17]==T[6],接着比较S[16]和T[5],发现S[16]==T[5],然后依次可以得到S[15]==T[4], S[14]==T[3], 直至S[13]!=T[2]。 根据坏字符规则, 子串应后移2-(-1)=3位;根据好后缀规则, 子串应后移6-0=6位;取较大的后移数,子串后移6位。
  • 第四轮比较中,S[21]!=T[7],但发现S[21]在子串T中,根据坏字符规则,将子串T后移6-4=2位,因为无好后缀,进入第五轮比较;
  • 第五轮比较中,依次自右向左比较,发现子串T与主串S全部匹配,模式匹配成功。

算法详解

为了能够使用程序实现上述算法,对坏字符和坏字符规则进行处理,形成坏字符表;对好后缀和好后缀规则进行处理,形成好后缀表。对于坏字符表的定义,可以根据坏字符的两种情况进行处理:

  • 主串中的坏字符在子串中找不到

将子串直接后移至坏字符的下一个位置。

  • 主串中的坏字符在子串中能找到

只需将主串中的坏字符与子串中的该字符对其便可,即将子串后移使得该“坏字符”与主串中的坏字符对齐。

坏字符规则: 后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置;
将坏字符规则使用公式表示出来便为bad[T[i]]-

ASCII A B C D E F G H I J K L M N O P Q R S T U V W X Y Z -
1 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
2 4 7 7 7 6 7 7 7 7 7 7 1 3 7 7 2 7 7 7 7 7 7 7 5 7 7 7
3 4 7 7 7 0 7 7 7 7 7 7 1 3 7 7 2 7 7 7 7 7 7 7 5 7 7 7

算法描述如下:

void BadC(String* T,int bad[]){
for(int i=0;i<ASIZE;i++){
bad[i]=T->length;
}
for(int i=0;i<T->length;i++){
bad[T->data[i]]=T->length-1-i;
}
}

...

具体代码见附件。


附件

#include<stdio.h>
#include<stdlib.h>

#define ASIZE 256 //ASCII_256
#define XSIZE 256
#define MaxSize 100
typedef char ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}String;


void StrCreat(String*);
void Print(String*);
void BadC(String*,int*);
void GoodS(String*,int*);
int BM(String*,String*,int*,int*);
void suffixes(String*,int*);


int main(int argc, char* argv[])
{
String *s;
s=(String*)malloc(sizeof(String));
StrCreat(s);

String *t;
t=(String*)malloc(sizeof(String));
StrCreat(t);


int bad[ASIZE]={0};
int good[XSIZE]={0};

BadC(t,bad);
GoodS(t,good);

int flag=BM(s,t,good,bad);
printf("\n");
if(flag!=-1){
printf("position:%d\n",flag+1);
}else{
printf("No find!\n");
}

return 0;
}

void StrCreat(String* S){
char x;
S->length=0;
printf("Please input String(End of '#'):\n");
scanf("%c",&x);
while(x!='#'){
S->data[S->length++]=x;
scanf("%c",&x);
}
getchar();
}

void Print(String *S){
for(int i=0;i<S->length;i++){
printf("%c",S->data[i]);
}
printf("\n");
}


int BM(String* S,String* T,int good[],int bad[]){
//int max;
int i=T->length-1;
int j=T->length-1;
while(j<S->length){
while(i!=0&&S->data[j]==T->data[i]){
--i;
--j;
}
if(i==0){
return j;
}else{
if(good[i]>bad[S->data[j]]){
j=j+good[i];
}else{
j=j+bad[S->data[j]];
}
// j += good[i]>bad[S->data[j]] ? good[i] : bad[S->data[j]];
i=T->length-1;
}
}
return -1;
}
void BadC(String* T,int bad[]){
for(int i=0;i<ASIZE;i++){
bad[i]=T->length;
}
for(int i=0;i<T->length;i++){
bad[T->data[i]]=T->length-1-i;
}
for(int i=0;i<T->length;i++){
printf("%4d",bad[T->data[i]]);
}
printf("\n");
}

void suffixes(String* T, int* suff){
suff[T->length-1]=T->length;
int q;
for(int i=T->length-2;i>=0;--i){
q=i;
while(q>=0&&T->data[q]==T->data[T->length-1-(i-q)]){
--q;
}
suff[i]=i-q;
}
for(int i=0;i<T->length;i++){
printf("%4d",suff[i]);
}
printf("\n");
}

void GoodS(String* T, int good[]){
int suff[XSIZE];

suffixes(T, suff);

for(int i=0;i<T->length;++i){
good[i]=T->length;
}
for(int i=T->length-1;i>= 0;--i){
if (suff[i]==i+1){
for (int j=0;j<T->length-1-i;++j){
if (good[j]==T->length){
good[j]=T->length-1-i;
}
}
}
}
for(int i=0;i<T->length-1;++i){
good[T->length-1-suff[i]]=T->length-1-i;
}

for(int i=0;i<T->length;i++){
printf("%4d",good[i]);
}
}

参考文献
Moore R S B S. Afaststringsearching algorithm[J]. Communications of the Acm, 1977, 20:762-772.
参考Blog
http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
http://blog.csdn.net/joylnwang/article/details/6785743
http://www.searchtb.com/2011/07/字符串匹配那些事(一).html