Chinaunix首页 | 论坛 | 博客
  • 博客访问: 473533
  • 博文数量: 59
  • 博客积分: 345
  • 博客等级: 二等列兵
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-18 22:44
个人简介

to be myself

文章分类

全部博文(59)

文章存档

2017年(5)

2013年(47)

2012年(3)

2011年(4)

分类: C/C++

2013-03-03 11:43:15

/*优于KMP算法的 BM改进算法——SUNDAY算法*/
例:
Hello, world. There is a word! No, it's two word.
word
H不等于w,patt移动。src[i+ patt_len]为o,next[‘o’]为4,移动四步到’o’。o不等于w,patt再移动4为o。o不等于w,再次移动到There前面的空格那,src[i + patt_len]为’r’,next[‘r’]为2,移动两步到’h’,再移动->’ ’->’a’,next[‘r’]为2。patt移动w,之后的o、r、d都匹配了。


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <string.h>

  3. void SUNDAY(char*src, char *patt)
  4. {
  5.     size_t patt_len = strlen(patt),src_len = strlen(src);
  6.     size_t next[256], i, m, match_len,succ = 0;
  7.     char*match_str;
  8.     
  9.     for(i=0;i<256; i++) //初始化next数组
  10.     {
  11.         next[i] = patt_len + 1;
  12.     }
  13.     for(i=0;i<patt_len; i++) //匹配到patternstring中的某个字符需要往后移动的步数
  14.     {
  15.         next[patt[i]] = patt_len - i;
  16.     }
  17.     
  18.     m = src_len - patt_len + 1;
  19.     for(i=0;i<m; i += next[src[i + patt_len]]) //根据src[i+ patt_len]这个字符判断移动的步数
  20.     {
  21.         if(src[i]== *patt)
  22.         {
  23.             match_str = src + i + 1;
  24.             match_len = 1;
  25.             do
  26.             {
  27.                 if(match_len== patt_len)
  28.                 {
  29.                     printf("Match at %dn", i);
  30.                     succ = 1;
  31.                     break;
  32.                 }
  33.             }
  34.             while(*match_str++== patt[match_len++]);
  35.         }
  36.     }
  37.     if(!succ)
  38.     {
  39.         printf("Hasnot matchn");
  40.     }
  41. }

  42. int main()
  43. {
  44.     charsrc[100] = "Hello, world. There is a word! No, it's two word.";
  45.     charpatt[10] = "word";
  46.     SUNDAY(src, patt);
  47.     return0;
  48. }

2011-05-12 20:24 发表于百度空间,今搬至CU。

 

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