Chinaunix首页 | 论坛 | 博客
  • 博客访问: 117350
  • 博文数量: 23
  • 博客积分: 495
  • 博客等级: 下士
  • 技术积分: 252
  • 用 户 组: 普通用户
  • 注册时间: 2011-08-05 20:44
文章分类
文章存档

2011年(23)

分类: C/C++

2011-08-08 13:18:29

设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t;不成功则指目标串s中不存在模式串t。

以下算法假设串采用顺序存储结构,即:
  1. #define MAXSIZE 50

  2. typedef struct
  3. {
  4.     char data[MAXSIZE];
  5.     int length;
  6. }SqString;

Brute-Force算法
    Brute-Force算法简称为BF算法,亦称为简单匹配算法,其基本思路是:从目标串s的第一个字符开始和模式串t中的第一个字符比较,若相等,则继续逐个比较后续的字符;否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。以此类推,若从模式串t的第i个字符开始,每个字符依次和目标串s中的对应字符相等,则匹配成功,该算法返回i;否则,匹配失败,算法返回-1 。

该算法C实现代码如下:
  1. int BFIndex(SqString *sp, SqString *tp)
  2. {
  3.     int i, j;
  4.     if(sp->length >= tp->length)
  5.     {
  6.         for(i = 0; i < sp->length; i++)
  7.         {
  8.             for(j = 0; j < tp->length && (i+j) < sp->length && sp->data[i+j] == tp->data[j]; j++);
  9.             if(j == tp->length) return(i);
  10.         }
  11.     }
  12.     return(-1);
  13. }


该算法的时间复杂度分析:
       假设目标串s的长度为m,模式串t的长度为n。第一个for循环的语句频度为m,第二个for循环的语句频度为n,故该算法的时间复杂度为O(mn),当然这是最坏的情况。该算法在最好情况下的时间复杂度为O(n)。
       该算法比较简单,易于理解,但效率不高,主要原因是:主串指针在若干字符序列比较相等后,若有一个字符比较不相等,需要回溯(主串指针的变化 i -> i+j -> i,回溯体现在i+j -> i这个过程,因为主串指针在第一个for循环每次执行i++时,都由i+j变为i,当然i+j >= i)。


例程:
  1. /*
  2. * file: Brute-Force.c
  3. * author: Jesse
  4. * date: 2011/08/07 13:15
  5. */

  6. #include <stdio.h>

  7. #define MAXSIZE 50

  8. typedef struct
  9. {
  10.     char data[MAXSIZE];
  11.     int length;
  12. }SqString;

  13. int BFIndex(SqString *sp, SqString *tp)
  14. {
  15.     int i, j;
  16.     if(sp->length >= tp->length)
  17.     {
  18.         for(i = 0; i < sp->length; i++)
  19.         {
  20.             for(j = 0; j < tp->length && (i+j) < sp->length && sp->data[i+j] == tp->data[j]; j++);
  21.             if(j == tp->length) return(i);
  22.         }
  23.     }
  24.     return(-1);
  25. }

  26. int main(void)
  27. {
  28.     SqString s, t;
  29.     int index;

  30.     printf("\n请输入目标串s和它的长度,以空格隔开,以回车键结束整个输入:\n");
  31.     scanf("%s %d", s.data, &s.length);
  32.     printf("请输入模式串t和它的长度,以空格隔开,以回车键结束整个输入:\n");
  33.     scanf("%s %d", t.data, &t.length);

  34.     index = BFIndex(&s, &t);

  35.     if(-1 == index) printf("\n匹配失败!\n");
  36.     else printf("\n匹配成功! i = %d\n", index);

  37.     return(0);
  38. }
阅读(2983) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:C和指针笔记1

给主人留下些什么吧!~~