Chinaunix首页 | 论坛 | 博客
  • 博客访问: 20748
  • 博文数量: 4
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 10
  • 用 户 组: 普通用户
  • 注册时间: 2014-01-11 10:40
文章分类

全部博文(4)

文章存档

2014年(4)

我的朋友

分类: LINUX

2014-08-16 13:58:25

原文地址:BM算法 作者:zzappled

后缀匹配,是指模式串的比较从右到左,模式串的移动也是从左到右的匹配过程,经典的BM算法其实是对后缀蛮力匹配算法的改进。所以还是先从最简单的后缀蛮力匹配算法开始。下面直接给出伪代码,注意这一行代码:j ;BM算法所做的唯一的事情就是改进了这行代码,即模式串不是每次移动一步,而是根据已经匹配的后缀信息,从而移动更多的距离。

1

j = 0;

2

while (j <= strlen(T) - strlen(P)) {

3

for (i = strlen(P) - 1; i >= 0 && P[i] ==T[i j]; --i)

4

if (i < 0)

5

match;

6

else

7

j;

8

}

为了实现更快移动模式串,BM算法定义了两个规则,好后缀规则和坏字符规则,如下图可以清晰的看出他们的含义。利用好后缀和坏字符可以大大加快模式串的移动距离,不是简单的 j,而是j =max (shift(好后缀), shift(坏字符))

先来看如何根据坏字符来移动模式串,shift(坏字符)分为两种情况:

  • 坏字符没出现在模式串中,这时可以把模式串移动到坏字符的下一个字符,继续比较,如下图:

  • 坏字符出现在模式串中,这时可以把模式串第一个出现的坏字符和母串的坏字符对齐,当然,这样可能造成模式串倒退移动,如下图:

为了用代码来描述上述的两种情况,设计一个数组bmBc['k'],表示坏字符‘k’在模式串中出现的位置距离模式串末尾的最大长度,那么当遇到坏字符的时候,模式串可以移动距离为: shift(坏字符) = bmBc[T[i]]-(m-1-i)。如下图:

数组bmBc的创建非常简单,直接贴出代码如下:

1

void preBmBc(char *x, int m, int bmBc[]) {

2

int i;

3

for (i = 0; i < ASIZE; i)

4

bmBc[i] = m;

5

for (i = 0; i < m - 1; i)

6

bmBc[x[i]] = m - i - 1;

7

}

再来看如何根据好后缀规则移动模式串,shift(好后缀)分为三种情况:

  • 模式串中有子串匹配上好后缀,此时移动模式串,让该子串和好后缀对齐即可,如果超过一个子串匹配上好后缀,则选择最靠左边的子串对齐。

  • 模式串中没有子串匹配上后后缀,此时需要寻找模式串的一个最长前缀,并让该前缀等于好后缀的后缀,寻找到该前缀后,让该前缀和好后缀对齐即可。

  • 模式串中没有子串匹配上后后缀,并且在模式串中找不到最长前缀,让该前缀等于好后缀的后缀。此时,直接移动模式到好后缀的下一个字符。

为了实现好后缀规则,需要定义一个数组suffix[],其中suffix[i] = s 表示以i为边界,与模式串后缀匹配的最大长度,如下图所示,用公式可以描述:满足P[i-s, i] == P[m-s, m]的最大长度s。

构建suffix数组的代码如下:

1

suffix[m-1]=m;

2

for (i=m-2;i>=0;--i){

3

q=i;

4

while(q>=0&&P[q]==P[m-1-i q])

5

--q;

6

suffix[i]=i-q;

7

}

有了suffix数组,就可以定义bmGs[]数组,bmGs[i] 表示遇到好后缀时,模式串应该移动的距离,其中i表示好后缀前面一个字符的位置(也就是坏字符的位置),构建bmGs数组分为三种情况,分别对应上述的移动模式串的三种情况

  • 模式串中有子串匹配上好后缀

  • 模式串中没有子串匹配上好后缀,但找到一个最大前缀

  • 模式串中没有子串匹配上好后缀,但找不到一个最大前缀

构建bmGs数组的代码如下:

01

void preBmGs(char *x, int m, int bmGs[]) {

02

int i, j, suff[XSIZE];

03

suffixes(x, m, suff);

04

for (i = 0; i < m; i)

05

bmGs[i] = m;

06

j = 0;

07

for (i = m - 1; i >= 0; --i)

08

if (suff[i] == i 1)

09

for (; j < m - 1 - i; j)

10

if (bmGs[j] == m)

11

bmGs[j] = m - 1 - i;

12

for (i = 0; i <= m - 2; i)

13

bmGs[m - 1 - suff[i]] = m - 1 - i;

14

}

再来重写一遍BM算法:

1

j = 0;

2

while (j <= strlen(T) - strlen(P)) {

3

for (i = strlen(P) - 1; i >= 0 && P[i] ==T[i j]; --i)

4

if (i < 0)

5

match;

6

else

7

j = max(bmGs[i], bmBc[T[i]]-(m-1-i));

8

}

考虑模式串匹配不上母串的最坏情况,后缀蛮力匹配算法的时间复杂度最差是O(n×m),最好是O(n),其中n为母串的长度,m为模式串的长度。

 

#include

#include

#define XSIZE 8

#define ASIZE 256

void preBmBc(char *x, int bmBc[])

{

 int m;

 int i;

 m = strlen(x);

 for (i = 0; i < ASIZE; i )

 {

  bmBc[i]=m;

 }

 for (i = 0; i < m - 1; i )

 {

  bmBc[x[i]]=m-1-i;

 }

}

 

void suffixes(char *x, int *suff)

{

 int i;

 int f;

 int g;

 int m;

 

 m = strlen(x);

 f = 0;

 suff[m-1] = m;

 g = m - 1;

 for (i = m - 2; i >= 0; --i)

 {

  if (i > g && suff[(m-1)-(f-i)] < i - g)

  {

   suff[i] = suff[(m-1)-(f-i)];

  }

  else

  {

   if (i < g)

    g=i;

   f=i;

   while (g >= 0 && x[g] == x[g m - 1 -f])

   {

    g--;

   }

   suff[i] = f - g;

  }

 }

}

 

void preBmGs(char *x, int bmGs[])

{

 int i;

 int j;

 int suff[XSIZE];

 int m;

 

 m=strlen(x);

 suffixes(x, suff);

 

 for (i = 0; i < m; i)

 {

  bmGs[i] = m;

 }

 

 j = 0;

 

 for (i = m-1;i >= 0; --i)

 {

  if (suff[i] == i 1)

  {

   for (; j < m - 1 - i; j)

   {

    if (bmGs[j] == m)

    {

     bmGs[j] = m - 1 - i;

    }

   }

  }

 }

 for (i = 0; i <= m-2; i)

 {

  bmGs[m - 1 -suff[i]]= m - 1 - i;

 }

}

int BM(char *x,char *y)

{

 int m;//模式串的长度

 int n;//目标串的长度

 

 int i;//模式串中匹配的位置

 int j;//目标串中匹配的位置

 

 int bmGs[XSIZE];//好后缀表

 int bmBc[ASIZE];//坏字符表

 

 preBmBc(y, bmBc);

 preBmGs(y, bmGs);

 

 m = strlen(y);

 n = strlen(x);

 

 j=0;

 while (j < n-m )

 {

  for (i = m - 1; i >= 0 && y[i] == x[i j]; --i);

 

  if (i < 0)

  {

   return j;

  }

  else

  {

   j = (bmGs[i]) > (bmBc[x[i j]] -m 1 i) ? (bmGs[i]) : (bmBc[x[i j]] -m 1 i);

  }

 }

 if (j>=n-m)

 {

  return -1;

 }

}

int main(int argc,char **argv)

{

        int ret;

        ret=BM(argv[1],argv[2]);

        printf("ret is %d\n",ret);

        return 0;

}

阅读(1153) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~