字符串的模式匹配詳解--BF算法與KMP算法

PC教程網】關于字符串的模式匹配詳解--BF算法與KMP算法_BF算法介紹:一.BF算法 BF算法是普通的模式匹配算法,BF算法的思想就是將目標串S的第一個字符與模式串P的第一個字符進行匹配,若相等,則繼續比較S的第二個字符和P的第二個字符;若不相等,則,下面小編為您針對字符串的模式匹配詳解--BF算法與KMP算法進行分享:

一.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;
}

相關教程

C語言實現字符串匹配KMP算法

C語言實現字符串匹配KMP算法

字符串匹配是計算機的基本任務之一。 舉例來說,有一個字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一個字符串"ABCDABD"? 下面的的KMP算法的解釋步驟 1. 首先,字符串"BBC …

eXeScope注冊碼算法bat版

eXeScope的官方網站是: http://hp.vector.co.jp/authors/VA003525/emysoft.htm 除了eXeScope以外還有一些其他的軟件,不過似乎不怎么出名。 eXeScope漢化特別版下載地址 http://www.jb51.net/softs/32587.html 正確的 …

python二分查找算法的遞歸實現方法

本文實例講述了python二分查找算法的遞歸實現方法。分享給大家供大家參考,具體如下: 這里先提供一段二分查找的代碼: def binarySearch(alist, item): first = 0 last =len(alist)-1 found = False wh …

Python求算數平方根和約數的方法匯總

一、求算術平方根 a=x=int(raw_input('Enter a number:'))if x = :while a*a x:a = a + if a*a != x:print x,'is not a perfect square'else:print aelse:print x,'is a negative number' 二、求約數 方法一: divisor = [ ]x=int(raw_input …

python裝飾器與遞歸算法詳解

1、python裝飾器 剛剛接觸python的裝飾器,簡直懵逼了,直接不懂什么意思啊有木有,自己都忘了走了多少遍Debug,查了多少遍資料,猜有點點開始明白了。總結了一下解釋得比較好的,通 …

python實現RSA加密(解密)算法

python實現RSA加密(解密)算法

RSA是目前最有影響力的公鑰加密算法,它能夠抵抗到目前為止已知的絕大多數密碼攻擊,已被ISO推薦為公鑰數據加密標準。 今天只有短的RSA鑰匙才可能被強力方式解破。到2008年為止, …

python實現中文分詞FMM算法實例

本文實例講述了python實現中文分詞FMM算法。分享給大家供大家參考。具體分析如下: FMM算法的最簡單思想是使用貪心算法向前找n個,如果這n個組成的詞在詞典中出現,就ok,如果沒有 …

python計算文本文件行數的方法

本文實例講述了python計算文本文件行數的方法。分享給大家供大家參考。具體實現方法如下: filename = "somefile.txt" myfile = open(filename) lines = len(myfile.readlines()) print "There are %d lines in %s" % …

Python實現LRU算法的2種方法

LRU:least recently used,最近最少使用算法。它的使用場景是:在有限的空間中存儲對象時,當空間滿時,會按一定的原則刪除原有的對象,常用的原則(算法)有LRU,FIFO,LFU等。在計算 …

Python 26進制計算實現方法

本文實例講述了Python 26進制計算方法。分享給大家供大家參考。具體分析如下: 題目是這樣的: 假設A=1,B=2,C=3...AA=27,AB=28...AAA=xxx(表示某個數字),寫一個函數統計一個字符串的值是多少 …

内蒙古十一选五任五推荐号