posts - 71,  comments - 41,  trackbacks - 0
字符串无回溯BM匹配算法
接着来个无回溯的，一般教科书上都是用KMP作case的，这里给个平均效率更好的Boyer-Moore Algorithm实现
 1 #include  < cstring >
 2 int  BM( const   char   * text,  const   char   * pattern)
  3 {
  4      int  arrShiftTable[ 256 ];
  5      int  tLen  =  strlen(text);
  6      int  pLen  =  strlen(pattern);
  7      int  currPos, tReadPos, pReadPos;
  8
 9      // exclude NUL
10      for  ( int  i  =   1 ; i  <   sizeof  arrShiftTable  /   sizeof  ( int ); i ++ )
 11      {
 12         arrShiftTable[i]  =  pLen;
 13     }
14
15      // exclude the last char in pattern
16      for  ( int  i  =   0 ; i  <  pLen  -   1 ; i ++ )
 17      {
 18         arrShiftTable[pattern[i]]  =  pLen  -   1   -  i;
 19     }
20
21      for  (currPos  =  pLen  -   1 ; currPos  <  tLen;  /* null */ )
 22      {
 23          for  (pReadPos  =  pLen  -   1 , tReadPos  =  currPos;
 24             pReadPos  >=   0   &&  pattern[pReadPos]  ==  text[tReadPos];
 25             pReadPos -- , tReadPos -- )
 26              /* null */ ;
 27
28          if  (pReadPos  <   0 )
 29          {
 30              return  tReadPos  +   1 ;
 31         }  
 32          else
33          {
 34             currPos  +=  arrShiftTable[text[currPos]];
 35         }
36
37     } // outer for
38
39      return   - 1 ;
 40 }
算法原理就不细说了，有兴趣可以google一下，主要思想就是从模式串的最后一个字母向前比较。此处需要使用一个跳转表，以便查询不匹配时模式串前进的步数。
posted on 2006-11-16 18:03 Charles 阅读(1016) 评论(1)  编辑 收藏 引用 所属分类: 面试小算法

FeedBack:
# re: 字符串无回溯BM匹配算法
2006-11-16 23:05 | 海上冰魂
汗。完全看不懂：（  回复  更多评论
  

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


Copyright ©2024 Charles Powered By: 博客园 模板提供：沪江博客
<2006年11月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

决定开始写工作日记，记录一下自己的轨迹...

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

  •  

积分与排名

  • 积分 - 48800
  • 排名 - 453

最新评论

阅读排行榜

评论排行榜