随笔 - 62  文章 - 257  trackbacks - 0
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

I Love Programming & Music.... CS Became CSed....

常用链接

留言簿(7)

随笔分类(64)

随笔档案(62)

文章分类(11)

文章档案(11)

相册

BlOoD

FriEnds

搞起的人们

搜索

  •  

积分与排名

  • 积分 - 111532
  • 排名 - 216

最新评论

阅读排行榜

评论排行榜

    今天上课老师讲了 KMP 的模式匹配算法,看了觉得很不错,不过当 KMP next 数组全为 -1 时,就退化成了朴素的模式匹配,觉得蛮郁闷的,后来自己看了 BM 匹配算法,感觉比 KMP 要好些,嘿嘿……

关于 KMP 算法,好像 Optimistic 写了一篇文章,我在此就不说了,大家有兴趣可以去看看:
    http://www.cppblog.com/sicheng/archive/2006/10/10/13537.html

思想:

假设给定模式串 ”bomb” 和字符串 “universal_super_bomb” ,在进行匹配的时候从最后一个开始比较:

T: universal_super_bomb

P: bomb

很明显, e 在模式串中根本不存在,那么最优的下一步匹配就应该是:

T: universal_ super _bomb

P:       bomb

这样显然效率就要比 KMP 高,而这就是 BM 匹配算法的思想。

 

方法:

现在那模式串 “bomb” 来举例,模式串长度 m=4

BM 模式匹配中有 2 个数组,定一个是 n1 ,一个是 n2

n1 的作用是记录字符集中的每个字符在模式中相对于最右端的最近距离, b 离最右端的为 0 m 1 o 2 ,其他没有出现的则为 4 ,那么 n1[27]={4,0,4,4,4,4,4,4,4,4,4,4,1,4,2,4,4,4,4,4,4,4,4,4,4,4,4} ’_’ n[26] )。

n2的作用是存储模式中第i个字符不等时,可以移动的位数。
    考虑模式串的子串
s=pi+1 pi+1 …p4 ,相对于模式串本身而言依次向左移动,如果子串 s 没有匹配上,则继续移动子串 s ,直到匹配或者移出模式串最左端,设(匹配或移出) + 之前 子串 s 移动的位数为 n ,则有 n2[i]=m-i+n-1 ,并且令 n2[m-1]=1 。那么对于模式串 ”bomb” 来说 n2[4]={4,4,4,1} 。( 看这里花了我好久的时间哦,明明是 C++ 数据结构,里面其他地方的下标是从 0 开始,而这里却是从 1 开始,晕死……)

接下来就是如何匹配。匹配的时候先把目标串和模式串左对齐,然后从模式串最右端开始比较, pi tj 不相等则计算 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i]) ,并将模式 P 右移 k+i-m 位,用 pm-1 tj+k 继续比较。

比如:

T: universal_super_bomb

P: bomb

p[3]!=t[3] ,那么 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i])=max(4,1)=4 ,则将模式串右移 k+(i+1)-m=4+4-4=4 位, j+k=3+4=7 p[3] t[7] 进行比较:

T: universal_super_bomb

P:     bomb

p[3]!=t[7] ,那么 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i])=max(4,1)=4 ,则将模式串右移 k+(i+1)-m=4+4-4=4 位, j+k=7+4=11 p[3] t[11] 进行比较:

T: universal_super_bomb

P:           bomb

p[3]!=t[11] ,那么 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i])=max(4,1)=4 ,则将模式串右移 k+(i+1)-m=4+4-4=4 位, j+k=11+4=15 p[3] t[15] 进行比较:

T: universal_super_bomb

P:                 bomb

p[3]!=t[15] ,那么 k=max(n1[(‘a’<=t[j]&&t[j]<=’z’)?(t[j]-‘a’):26],n2[i])=max(4,1)=4 ,则将模式串右移 k+(i+1)-m=4+4-4=4 位, j+k=15+4=11 p[3] t[15] 进行比较:

T: universal_super_bomb

P:                        bomb

匹配成功。

(例子有点差哦,没有体现 n1 n2 的作用,不好意思啊,各位,原谅我吧…… 偷个懒,懒得换了……)

实现:

再次偷懒,这次不想写,下次写吧,嘿嘿……

posted on 2006-10-11 20:45 Asp 阅读(3329) 评论(3)  编辑 收藏 引用 所属分类: Ar!thmEt!c

FeedBack:
# re: BM匹配算法 2007-02-08 20:52 伟大
太杂乱,看不懂  回复  更多评论
  
# re: BM匹配算法[未登录] 2008-10-28 11:46 r
靠,垃圾,自己不都懂!  回复  更多评论
  
# re: BM匹配算法 2009-05-31 20:38 0
还有错误。。。
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理