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

2014-06-17  来源:本站原创  分类:C 语言  人气:0 

这篇文章记录一下串里面的模式匹配,模式匹配,顾名思义就是给定一个被匹配的字符串,然后用一个字符串模式(模型)去匹配上面说的字符串,看后者是否在前者里面出现。常用的有2种算法可以实现,下面我们来具体探讨下

一.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<strlen(s))
  {
    j=0;
    while(s[i]==p[j]&&j<strlen(p))
    {
      i++;
      j++;
    }
    if(j==strlen(p))
      return i-strlen(p);
    i=i-j+1;        //指针i回溯
  }
  return -1;
}

  其实在上面的匹配过程中,有很多比较是多余的。在第五趟匹配失败的时候,在第六趟,i可以保持不变,j值为2。因为在前面匹配的过程中,对于串S,已知s0s1s2s3=p0p1p2p3,又因为p0!=p1!,所以第六趟的匹配是多余的。又由于p0==p2,p1==p3,所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。

二.KMP算法

KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。
  在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
  对于next[]数组的定义如下:
 1) next[j] = -1 j = 0
 2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
 3) next[j] = 0 其他
 如:
 P a b a b a
 j 0 1 2 3 4
next -1 0 0 1 2
 即next[j]=k>0时,表示P[0...k-1]=P[j-k,j-1]
 因此KMP算法的思想就是:在匹配过程称,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。
代码实现如下:

int KMPMatch(char *s,char *p)
{
  int next[100];
  int i,j;
  i=0;
  j=0;
  getNext(p,next);
  while(i<strlen(s))
  {
    if(j==-1||s[i]==p[j])
    {
      i++;
      j++;
    }
    else
    {
      j=next[j];    //消除了指针i的回溯
    }
    if(j==strlen(p))
      return i-strlen(p);
  }
  return -1;
}

  因此KMP算法的关键在于求算next[]数组的值,即求算模式串每个位置处的最长后缀与前缀相同的长度, 而求算next[]数组的值有两种思路,第一种思路是用递推的思想去求算,还有一种就是直接去求解。
1.按照递推的思想:
根据定义next[0]=-1,假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]
1)若P[j]==P[k],则有P[0..k]==P[j-k,j],很显然,next[j+1]=next[j]+1=k+1;
2)若P[j]!=P[k],则可以把其看做模式匹配的问题,即匹配失败的时候,k值如何移动,显然k=next[k]。
因此可以这样去实现:

void getNext(char *p,int *next)
{
  int j,k;
  next[0]=-1;
  j=0;
  k=-1;
  while(j<strlen(p)-1)
  {
    if(k==-1||p[j]==p[k])  //匹配的情况下,p[j]==p[k]
    {
      j++;
      k++;
      next[j]=k;
    }
    else          //p[j]!=p[k]
      k=next[k];
  }
}

2.直接求解方法

void getNext(char *p,int *next)
{
  int i,j,temp;
  for(i=0;i<strlen(p);i++)
  {
    if(i==0)
    {
      next[i]=-1;   //next[0]=-1
    }
    else if(i==1)
    {
      next[i]=0;   //next[1]=0
    }
    else
    {
      temp=i-1;
      for(j=temp;j>0;j--)
      {
        if(equals(p,i,j))
        {
          next[i]=j;  //找到最大的k值
          break;
        }
      }
      if(j==0)
        next[i]=0;
    }
  }
}
bool equals(char *p,int i,int j)   //判断p[0...j-1]与p[i-j...i-1]是否相等
{
  int k=0;
  int s=i-j;
  for(;k<=j-1&&s<=i-1;k++,s++)
  {
    if(p[k]!=p[s])
      return false;
  }
  return true;
}
相关文章
  • 字符串的模式匹配详解--BF算法与KMP算法 2014-06-17

    这篇文章记录一下串里面的模式匹配,模式匹配,顾名思义就是给定一个被匹配的字符串,然后用一个字符串模式(模型)去匹配上面说的字符串,看后者是否在前者里面出现.常用的有2种算法可以实现,下面我们来具体探讨下 一.BF算法 BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符:若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果. 举例说明: S: ababcababa P

  • php中字符串和正则表达式详解 2014-01-11

    这篇文章主要介绍了php中字符串和正则表达式详解,需要的朋友可以参考下 一.字符串类型的特点 1.PHP是弱类型语言,其他数据类型一般都可以直接应用于字符串函数操作. <?phpecho substr("123456",2,4); //输出345echo substr(123456,2,4); //输出345echo hello; //先查找hello常量,若没找到,将hello看做字符串使用?> 2.字符串可以作为"数组",是字符的集合. <?p

  • Swift教程之字符串和字符详解 2014-03-16

    这篇文章主要介绍了Swift教程之字符串和字符详解,本文讲解了字符串常量.初始化一个空串.变长字符串.字符串不是指针,而是实际的值.字符等内容,需要的朋友可以参考下 一个字符串String就是一个字符序列,像"hello,world","albatross"这样的.Swift中的字符串是用String关键词来定义的,同时它也是一些字符的集合,用Character定义. Swift的String和Character类型为代码提供了一个快速的,兼容Unicode的字符解

  • PHP中strtr字符串替换用法详解 2014-03-26

    这篇文章主要介绍了PHP中strtr字符串替换用法,以大量实例详细解读了strtr字符串替换的用法与技巧,并与str_replace做了对比以加深理解,需要的朋友可以参考下 本文实例讲述了PHP中strtr字符串替换用法.分享给大家供大家参考.具体分析如下: strtr(string,from,to)或者strtr(string,array) 首先针对strtr函数第一种方式,我们看看下面的举例,代码如下: <?php echo strtr("I Love you","

  • c语言字符数组与字符串的使用详解 2013-11-24

    本篇文章是对c语言中字符数组与字符串的使用进行了详细的分析介绍,需要的朋友参考下 1.字符数组的定义与初始化字符数组的初始化,最容易理解的方式就是逐个字符赋给数组中各元素. char str[10]={ 'I',' ','a','m',' ','h','a','p','p','y'}; 即把10个字符分别赋给str[0]到str[9]10个元素 如果花括号中提供的字符个数大于数组长度,则按语法错误处理:若小于数组长度,则只将这些字符数组中前面那些元素,其余的元素自动定为空字符(即 '' ). 2

  • Asp.net,C# 加密解密字符串的使用详解 2014-10-22

    本篇文章对Asp.net,C# 加密解密字符串的使用进行了详细的分析介绍,需要的朋友参考下 首先在web.config | app.config 文件下增加如下代码: <?xml version="1.0"?> <configuration> <appSettings> <add key="IV" value="SuFjcEmp/TE="/> <add key="Key"

  • KMP算法详解 2012-10-25

    如果机房马上要关门了,或者你急着要和MM约会,请直接跳到第六个自然段. 我们这里说的KMP不是拿来放电影的(虽然我很喜欢这个软件),而是一种算法.KMP算法是拿来处理字符串匹配的.换句话说,给你两个字符串,你需要回答,B串是否是A串的子串(A串是否包含B串).比如,字符串A="I'm matrix67",字符串B="matrix",我们就说B是A的子串.你可以委婉地问你的MM:"假如你要向你喜欢的人表白的话,我的名字是你的告白语中的子串吗?" 解

  • 深入理解JavaScript系列(33):设计模式之策略模式详解 2014-04-04

    这篇文章主要介绍了深入理解JavaScript系列(33):设计模式之策略模式详解,策略模式定义了算法家族,分别封装起来,让他们之间可以互相替换,此模式让算法的变化不会影响到使用算法的客户,需要的朋友可以参考下 介绍 策略模式定义了算法家族,分别封装起来,让他们之间可以互相替换,此模式让算法的变化不会影响到使用算法的客户. 正文 在理解策略模式之前,我们先来一个例子,一般情况下,如果我们要做数据合法性验证,很多时候都是按照swith语句来判断,但是这就带来几个问题,首先如果增加需求的话,我们还要

  • 六之再续:KMP算法之总结篇(必懂KMP) 2014-09-14

    引记 此前一天,一位MS的朋友邀我一起去与他讨论快速排序,红黑树,字典树,B树.后缀树,包括KMP算法,唯独在讲解KMP算法的时候,言语磕磕盼盼,我想,原因有二:1.博客内的东西不常回顾,忘了不少:2.便是我对KMP算法的理解还不够彻底,自不用说讲解自如,运用自如了.所以,特再写本篇文章.由于此前,个人已经写过关于KMP算法的两篇文章,所以,本文名为:KMP算法之总结篇. 本文分为二个部分:第一部分.再次回顾普通的BF算法与KMP算法各自的时间复杂度,并两相对照各自的匹配原理:第二部分.通过我此

  • C语言kmp算法简单示例和实现原理探究 2015-04-26

    这篇文章主要介绍了C语言kmp算法简单示例和实现原理探究,本文用简洁的语言说明KMP算法的原理,并给出了示例,需要的朋友可以参考下 以前看过kmp算法,当时接触后总感觉好深奥啊,抱着数据结构的数啃了一中午,最终才大致看懂,后来提起kmp也只剩下"奥,它是做模式匹配的"这点干货.最近有空,翻出来算法导论看看,原来就是这么简单(下不说程序实现,思想很简单). 模式匹配的经典应用:从一个字符串中找到模式字串的位置.如"abcdef"中"cde"出现在原

  • 简单有效的kmp算法 2013-10-24

    以前看过kmp算法,当时接触后总感觉好深奥啊,抱着数据结构的数啃了一中午,最终才大致看懂,后来提起kmp也只剩下"奥,它是做模式匹配的"这点干货.最近有空,翻出来算法导论看看,原来就是这么简单(下不说程序实现,思想很简单). 模式匹配的经典应用:从一个字符串中找到模式字串的位置.如"abcdef"中"cde"出现在原串第三个位置.从基础看起 朴素的模式匹配算法 A:abcdefg B:cde 首先B从A的第一位开始比较,B++==A++,如果全部

  • 扩展KMP算法(Extend KMP) 2014-08-16

    我们这里说的KMP不是拿来放电影的(虽然我很喜欢这个软件),而是一种算法.KMP算法是拿来处理字符串匹配的.今天我们谈到的是对KMP算法的拓展 扩展kmp既是求模式串和主串的每一个后缀的最长公共前缀 即令s[i]表示主串中以第i个位置为起始的后缀,则B[i]表示s[i]和模式串的最长公共前缀 显然KMP是求s[i]=模式串长度的情况,所以,扩展KMP是对KMP的拓展 像求KMP的next数组一样,我们先求A[i],表示模式串的后缀和模式串的最长公共前缀 然后再利用A[i]求出B[i] 说明一下A

  • 计算机中的字符串编码.乱码.BOM等问题详解 2013-12-18

    这篇文章主要介绍了计算机中的字符串编码.乱码.BOM等问题详解,对文件编码.vim乱码.什么情况下会出现乱码.字符编码的发展历史.字符集和编码的区别.汉字ANSI编码的发展历史.BOM头等问题做了全面总结.详细介绍,需要的朋友可以参考下 因为电脑是windows 7系统,开发环境又在linux,经常在linux碰到乱码问题,很是痛苦,于是决定好好了解编码的来龙气脉,并分享个各位,免得出现乱码时不知所措. 是否存在文件编码 在讲解字符编码之前,我们需先明确文件本身没有编码一说,只有文字才有编码的概

  • AC自动机算法详解 2013-12-24

    AC自动机算法详解 首先简要介绍一下 AC 自动机: Aho-Corasick automation ,该算法在 1975 年产生于贝尔实验室,是著名的多模匹配算法之一.一个常见的例子就是给出 n 个单词,再给出一段包含 m 个字符的文章,让你找出有多少个单词在文章里出现过.要搞懂 AC 自动机,先得有模式树(字典树) Trie 和 KMP 模式匹配算法的基础知识. AC 自动机算法分为 3 步:构造一棵 Trie 树,构造失败指针和模式匹配过程. 如果你对KMP算法和了解的话,应该知道KMP算

  • 算法之排列算法与组合算法详解 2014-08-23

    这篇文章主要介绍了算法之排列算法与组合算法详解,本文以字典序法.递归法为例讲解了排列算法.全组合算法等,需要的朋友可以参考下 1. 前言 本文介绍了常用的排列组合算法,包括全排列算法,全组合算法,m个数选n个组合算法等. 2. 排列算法 常见的排列算法有: (A)字典序法 (B)递增进位制数法 (C)递减进位制数法 (D)邻位对换法 (E)递归法 介绍常用的两种: (1) 字典序法 对给定的字符集中的字符规定了一个先后关系,在此基础上按照顺序依次产生每个排列. [例]字符集{1,2,3},较小的

  • 基于一致性hash算法 C++语言的实现详解 2014-09-19

    在<基于一致性hash算法(consistent hashing)的使用详解>一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现 一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择. 首先来谈一下一致性hash算法中用于存储结点的数据结构.通过了解一致性hash的原理,我们知道结点可以想象为是存储在一个环形的数据结构上(如下图),结点A.B.C.D按has

  • Python 字符串方法详解 2012-04-24

    Python 字符串方法详解 本文最初发表于赖勇浩(恋花蝶)的博客(http://blog.csdn.net/lanphaday),如蒙转载,敬请保留全文完整,切勿去除本声明和作者信息. 在编程中,几乎90% 以上的代码都是关于整数或字符串操作,所以与整数一样,Python 的字符串实现也使用了许多拿优化技术,使得字符串的性能达到极致.与 C++ 标准库(STL)中的 std::string 不同,python 字符串集合了许多字符串相关的算法,以方法成员的方式提供接口,使用起来非常方便. 字符

  • 算法详解之分治法具体实现 2013-10-13

    这篇文章主要介绍了算法详解之分治法具体实现,需要的朋友可以参考下 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同.求出子问题的解,就可得到原问题的解. 分治法解题的一般步骤: (1)分解,将要解决的问题划分成若干规模较小的同类问题: (2)求解,当子问题划分得足够小时,用较简单的方法解决: (3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解. 一言以蔽之:分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同

  • 数据挖掘之Apriori算法详解和Python实现代码分享 2013-10-16

    这篇文章主要介绍了数据挖掘之Apriori算法详解和Python实现代码分享,本文先是对Apriori算法做了详细介绍,然后给出了Python版实现代码,需要的朋友可以参考下 关联规则挖掘(Association rule mining)是数据挖掘中最活跃的研究方法之一,可以用来发现事情之间的联系,最早是为了发现超市交易数据库中不同的商品之间的关系.(啤酒与尿布) 基本概念 1.支持度的定义:support(X-->Y) = |X交Y|/N=集合X与集合Y中的项在一条记录中同时出现的次数/数据记

  • Javascript数据结构与算法之列表详解 2013-11-12

    这篇文章主要介绍了Javascript数据结构与算法之列表详解,本文讲解了列表的抽象数据类型定义.如何实现列表类等内容,需要的朋友可以参考下 前言:在日常生活中,人们经常要使用列表,比如我们有时候要去购物时,为了购物时东西要买全,我们可以在去之前,列下要买的东西,这就要用的列表了,或者我们小时候上学那段时间,每次考完试后,学校都会列出这次考试成绩前十名的同学的排名及成绩单,等等这些都是列表的列子.我们计算机内也在使用列表,那么列表适合使用在什么地方呢?不适合使用在什么地方呢? 适合使用在:当列表