当前位置:  编程技术>c/c++/嵌入式

字符串的模式匹配详解--BF算法与KMP算法

    来源: 互联网  发布时间:2014-10-27

    本文导语:  一.BF算法     BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符...

一.BF算法
    BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。

   举例说明:

  S: ababcababa
  P: ababa
  BF算法匹配的步骤如下
      i=0                  i=1               i=2             i=3             i=4
 第一趟:ababcababa     第二趟:ababcababa   第三趟:ababcababa  第四趟:ababcababa  第五趟:ababcababa
       ababa              ababa             ababa            ababa            ababa
      j=0                  j=1              j=2             j=3             j=4(i和j回溯)
       i=1                 i=2              i=3              i=4            i=3
 第六趟:ababcababa     第七趟:ababcababa    第八趟:ababcababa   第九趟:ababcababa  第十趟:ababcababa
       ababa               ababa              ababa            ababa            ababa
       j=0                 j=0              j=1              j=2(i和j回溯)      j=0
       i=4                  i=5             i=6              i=7             i=8
第十一趟:ababcababa    第十二趟:ababcababa  第十三趟:ababcababa  第十四趟:ababcababa  第十五趟:ababcababa
           ababa                ababa              ababa             ababa             ababa
        j=0                  j=0             j=1              j=2             j=3
 
          i=9
第十六趟:ababcababa
            ababa
          j=4(匹配成功)

代码实现:

int BFMatch(char *s,char *p)
{
  int i,j;
  i=0;
  while(i

    
 
 

您可能感兴趣的文章:

  • "400分给有比较好的字符串比较的算法的朋友"要结帖,想做笔迹保留的不可漏看哦
  • 最大对称字符串的算法
  • php字符串哈希函数算法实现代码
  • 使用java自带des加密算法实现文件加密和字符串加密
  • C语言实现字符串匹配KMP算法
  • 帮忙看看这个shell脚本,用正则匹配字符串为什么匹配不上
  • 字符串的匹配和提取
  • 从字符串中 查找匹配字符串
  • grep匹配字符串
  • 关于里面字符串匹配的问题
  • 求字符串匹配的脚本
  • unix和windows的字符串类型是否匹配?
  • 如何把grep匹配的字符串 之间用换行分开 而不是空格
  • 用正则表达式怎么匹配最后一个字符串?
  • awk如何匹配以#开头的字符串?
  • awk 匹配字符串
  • grep命令怎么精确匹配文件中的字符串
  • 使用正则表达式匹配[***]样式的字符串
  • Shell下字符串匹配问题,谢谢
  • 字符串替换Replace仅替换第一个字符串匹配项
  • shell脚本中判断字符串匹配正则式的问题
  • java 字符串匹配函数
  • 怎样层级搜索匹配字符串
  • sed 替换指定行的匹配字符串,第一次发帖。
  • C#匹配中文字符串的4种正则表达式分享
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • C++ Strings(字符串) 成员 size():返回字符串中字符的数量
  • 关于字符串的操作,我想得到字符串的长度,和他开始两位组成的新的字符串,例如::
  • C++ Strings(字符串) 成员 c_str():将字符串以C字符数组的形式返回
  • 如何使GDB显示完整的字符串变量,当字符串比较长时。
  • C++ Strings(字符串) 成员 empty():如果字符串为空,返回真
  • java/j2ee iis7站长之家
  • C++ Strings(字符串) 成员 length():返回字符串的长度
  • 请教,有关16进制字符串形成2进制字符串的问题!
  • C++ Strings(字符串) 成员 resize():重新设置字符串的大小
  • shell程序:在大文件中查找特定字符串,但该字符串可以跨行
  • C++ Strings(字符串) 成员 Operators:操作符,用于字符串比较和赋值
  • 怎样判断一个字符串在另一个字符串里面?
  • C++ Strings(字符串) 成员 reserve():保留一定容量以容纳字符串(设置capacity值)
  • 请问怎样从键盘读入一个字符串,怎样连接两个字符串,谢谢
  • C++ Strings(字符串) 成员 swap():交换两个字符串的内容
  • 浅析string类字符串和C风格字符串之间的区别
  • C++ Strings(字符串) 成员 find():在字符串中查找字符
  • 如何用shell实现将指定文件中的指定的字符串替换为我指定的另外的字符串
  • C++ Strings(字符串) 成员 substr():返回某个子字符串
  • 如何将一个双引号”放在一个字符串中,就是在字符串中如何转义一个双引号。谢谢!
  • C++ Strings(字符串) 成员 end():返回一个迭代器,指向字符串的末尾。(最后一个字符的下一个位置)
  • mysql查询字符串替换语句小结(数据库字符串替换)




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3