關于字符串匹配算法研究

阿修羅之獅猿授 2016-09-11

展開全文

第一篇隨筆,，開始寫博客生涯。寫程序這么長時間，突然發(fā)現也要總結與積累,。原來想第一篇博文是關于以前寫的代碼研究,，發(fā)現還需要整理。這樣,，先發(fā)表一篇關于字符串

匹配的文章,。就這樣啦！

字符串匹配主要是關于模式串與主串匹配的問題,。關于這個問題,，有很多方法。網上也有不少例子,，借鑒了不少,，以下就介紹下面幾種算法。

（1）BF算法（常規(guī)算法）

BF算法就是最笨的算法,，一個一個進行匹配,。這里采用后綴匹配算法。其實與正常的BF算法想法差不多,。只不過為了與第四種算法相對應,，就用后綴匹配算法代替BF算法。

從網上搞些圖（自己實在不想自己畫圖）

從后面開始進行匹配,。當不匹配時,，子串整體向右偏移一個單位，再與主串進行比較,。從而不斷進行循環(huán),，直到比較到主串最后一個數。不匹配,，則返回-1,。否則，返回主

串開始匹配的位置,。

Source為主串,，SubString為子串。

 1 int Search_Reverse(const char *Source,const char *SubString)           //后綴綴回溯比較法  （常規(guī)BF算法）---為BM算法進行鋪墊
 2 {
 3   int SourceArry = strlen(Source);                                     //主串的長度
 4   int SubArry = strlen(SubString);                                     //子串的長度
 5   int pSub  ,pSour =  SubArry;                                         //定義pSub,pSour數值
 6   if(SubArry==0)
 7       return -1;
 8   while(pSour <= SourceArry)                                           //主串是否到了盡頭             
 9   {   
10       pSub = SubArry;                                                  //初始化
11       while(SubString[--pSub]==Source[--pSour])                        //進行匹配比較
12     {
13        if(pSour < 0)  return -1;                                       //如果pSour,以子串長度為一組的主串掃描結束
14            
15        if(pSub == 0) return  pSour;                                    //為0,匹配成功
16 
17     }
18     pSour += (SubArry - pSub) +1 ;                                     //進行偏移,pSour值進行恢復與回溯,SubArry - pSub為以前減去的值補回
19     
20   }
21 
22   return -1;
23 
24 }

(2)KMP算法

KMP算法可能一開始理解有點麻煩,。不過,，有些時候，就要想為什么用KMP匹配算法,。比如有子串“abcabd",為什么要用這算法,？

當主串中S[5]=“c"與子串T[5]"d"不匹配了，如果采用BF算法進行匹配,，則效率偏低,。采用KMP算法之后,，將子串中的T[0]與主串中的S[3]對齊，再進行比較,。因為在子串

中,，T[0]~T[1]的字符串與T[3]~T[4]相等,，那么剛才第一次匹配時,，已經說明S[3]~S[4]與T[3]~T[4]相等,那么也就說明S[3]~S[4]與T[0]~T[1]相等。所以直接將S[5]與

T[2]比較,，從這里開始匹配,。所以在第一次匹配失敗之后，決定從子串中哪個位置再開始進行比較,，就是KMP算法中關于Next[]數組的設置,。所以KMP算法比BF算法稍微簡單一

點，因為我們對于子串做了處理,，不用從有時不用從子串T[0]從頭開始比較,。

基于子串關于Next[]數組的處理，如下：

下標i	0	1	2	3	4	5	6	7	8	9
p(i)	a	b	c	d	a	a	b	c	a	b
next[i]	-1	0	0	0	0	1	1	2	3	1

Next[0]設置為-1,，說簡單一點,，就是在后面找到相匹配的最大前綴。這時,，T[4]與T[0]相等,。則如果在這里不匹配時，則直接T[Next[4]]與S[4]再進行比較,。當在S[5]時不

匹配時,，則回退到T[Next[5]]再進行比較。所以Next數組中的數字代表這個意思,，即可以回溯到哪里,。如果運氣好，有相同字符,，可以節(jié)約一定時間,。至于Next數組的算法，則可

以采用迭代,。

也就是對于序列

找出這樣一個k,，使其滿足

并且要求k盡可能的大！

 1 void NextNumber(int Next[],void*S,unsigned int ElemtSize)                    //對需要查找的字符串進行預處理
 2 {   
 3     
 4     char *ps = (char*) malloc(ElemtSize);
 5     memcpy(ps,S, ElemtSize);
 6     int i=strlen(ps);
 7     int j = 0;                       //從頭開始計數的j標識
 8     int p = 1;                       //與j進行比較的標識
 9     Next[0] = -1;                    //Next[0] = -1,Next[1] = 0;
10     Next[1] = 0;
11     while(p<i-1)                     //p<i-1,為循環(huán)限制條件
12     {
13         if(ps[p]==ps[j])   
14       {
15         Next[p+1] = j+1 ;            //最主要的區(qū)別在于,，Next[]為一數組,，ps又為一數組，且數組之間相差為一
16         ++p;
17         ++j;
18       }
19       else if(j==0)                  //當j為0時,，Next[p+1] = 0;這個有點初始化的味道,。         
20       {
21         Next[p+1] = 0;           
22         ++p;
23       
24       }
25       else 
26         j = Next[j];                 //數組適當進行回退
27     }
28       
29 }

Next數組處理好了,，接下來就是進行字符串匹配了，即主函數,。

 1 const int Max = 100;
 2 void NextNumber(int Next[],void*S,unsigned int ElemtSize);
 3 int KMP(void*T,void*S,unsigned int ElemtSizeT,unsigned int ElemtSizeS)        //T為主串,S為子串
 4 {
 5     char *Ts = (char*) malloc(ElemtSizeT);                                    //將Void做一個轉換
 6     memcpy(Ts,T,ElemtSizeT);
 7     char *Ps = (char*) malloc(ElemtSizeS);
 8     memcpy(Ps,S,ElemtSizeS);
 9     int Next[Max];
10     NextNumber(Next,S,ElemtSizeS);
11     int t = 0;
12     int s = 0;
13     int v;                                                                     //v為偏移距離
14     while(t < ElemtSizeT-1 && (s< ElemtSizeS-1)||s==-1)
15     {
16       if(s == -1|| Ts[t] == Ps[s])                                             //s為-1時,，即比較從頭開始,Ts為主串，Ps為子串
17       {
18           ++t;++s; 
19       }
20       else 
21        s = Next[s]; 
22       
23       if(s == ElemtSizeS-1) v = t-ElemtSizeS+1;
24       else  v = -1;
25     }
26 
27      return v;
28 }

上述代碼中,，字符類型為Void*,，不過下面為此做了轉換。為什么用此類型,，純屬作為實驗,，嘗試用void*類型寫一下，大家完全可以用char*.哈哈,！

如果還有什么不懂,，盡量百度，我發(fā)現自己的表達水平果然不怎么樣,！

(3)Rabin_Karp算法

這個算法是從《算法導論》中借鑒過來的,，主要是利用公式。相對來說,，前期的工作可能比較辛苦些,，主要是做一個Hash表，具體咋樣,？這里不具體說明,。

大概思想就是下面這個圖：

其實也就是不斷增加找到匹配子串的概率，但也有可能不是,，相對來說好一些,。當主串中某位置計算出來的值與整個子串計算出來的值相等時，就說明可能在主串這個位置,，與

子串相匹配,。有這個概率，降低了比較的次數,。

算法精華在于在于首先判斷出現子串首字母的地方進行標記,，然后再進行判斷比較

算法利用到了初等算法的理論，兩個數對于第三個數等價,。

 1 int Rabin_Karp_Match( string T,string P,int d,int q)          //d為基數/q為除數,最好是一個素數(T為主串,P為子串）
 2 {
 3   int n = T.length();
 4   int m = P.length();
 5   int h = d^(m-1);
 6   int v  ;                                                     //v為返回值（-1）為失敗,其他v值代表匹配的偏移量
 7   int p = 0;
 8   int t[Max];
 9   t[0] = 0;
10   for(int i=0;i<m;++i)
11   {
12      p=(d*p+P[i])%q;                                          //整個子串計算出來的值
13      t[0]=(d*t[0] +T[i])%q;                                   //t0為T主串首個開始點,，方便后面用迭代
14   }
15   for(int j=0;j<n-m;++j)
16   {
17       if(p==t[j])
18           for(int s=0;s<m;++s)
19           { 
20               if(P[s] != T[j]) break;
21               else if(s = m-1)  { v = j ; return v ;}
22               else {++s;++j;}
23           }
24       
25       if(j<n-m)
26           t[j+1] = (d*(t[j] -T[j+1]*h) +T[j+m])%q;
27   }
28 return -1;
29 
30 }

具體參照http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap34.htm

（4）BM算法

BM算法可能是相對來說，算法效率最高的一種,，一般是KMP算法的3~5倍,。

BM算法是從后綴比較法開始的。就是給出的算法（1）代碼,。然而,，普通的后綴比較法一般移動只有1,。而BM算法其實是對后綴蠻力匹配算法的改進。為了實現更快移動模式

串,，BM算法定義了兩個規(guī)則,，好后綴規(guī)則和壞字符規(guī)則。用好后綴和壞字符可以大大加快模式串的移動距離,，不是簡單的 j,，而是j =max (shift(好后綴), shift(壞字符))。

具體算法,，如下圖（網上百度別人博客中的圖）：

1,、壞字符算法（情況分為兩種）：

壞字符沒出現在模式串中，這時可以把模式串移動到壞字符的下一個字符,，繼續(xù)比較，如下圖：

壞字符出現在模式串中,，這時可以把模式串第一個出現的壞字符和母串的壞字符對齊,，當然，這樣可能造成模式串倒退移動,，如下圖：

為了用代碼來描述上述的兩種情況,，設計一個數組bmBc['k']，表示壞字符‘k’在模式串中出現的位置距離模式串末尾的最大長度,，那么當遇到壞字符的時候,，模式串可以移動距離為： shift(壞字符) = bmBc[T[i]]-（m-1-i)。如下圖：

2,、好后綴算法（分為三種情況）

模式串中有子串匹配上好后綴,，此時移動模式串，讓該子串和好后綴對齊即可,，如果超過一個子串匹配上好后綴,，則選擇最靠左邊的子串對齊。

模式串中沒有子串匹配上后后綴,，此時需要尋找模式串的一個最長前綴,，并讓該前綴等于好后綴的后綴，尋找到該前綴后,，讓該前綴和好后綴對齊即可,。

模式串中沒有子串匹配上后后綴，并且在模式串中找不到最長前綴,，讓該前綴等于好后綴的后綴,。此時，直接移動模式到好后綴的下一個字符,。

為了實現好后綴規(guī)則,，需要定義一個數組suffix[],，其中suffix[i] = s 表示以i為邊界，與模式串后綴匹配的最大長度,，如下圖所示,，用公式可以描述：滿足P[i-s, i] == P[m-s, m]的最大長度s,。

好后綴算法比較難理解,，理論解釋是：

好后綴數組（其中Suffx數組n內數字主要表示好后綴的最右邊下標與最左邊之間的差值）

i. 如果在P中位置t處已匹配部分P'在P中的某位置t'也出現，且位置t'的前一個字符與位置t的前一個字符不相同,，則將P右移使t'對應t方才的所在的位置,。

ii. 如果在P中任何位置已匹配部分P'都沒有再出現，則找到與P'的后綴P''相同的P的最長前綴x,，向右移動P,，使x對應方才P''后綴所在的位置。

關于好后綴算法：

 1  int *Suff = new int[SubLen];
 2   Suff[SubLen-1] = SubLen;                                   //Suff數組主要記錄以數組內標號為子串中的距離
 3 
 4   int *Suff2 = new int[SubLen];                              //Suff2數組主要記錄下標為以i為首字母的字符后綴離最近的匹配字符串的距離
 5   for(int i=0;i<SubLen;i++)
 6   Suff2[i] = 0;                                              //初始化為0
 7 
 8   
 9  for(int i=SubLen-2;i>=0;i--)
10   {
11     int k=i;
12     while(k>=0 && SubString[k] == SubString[SubLen-1-i+k])   //下標SubLen+k-1-i與k相對應(從后面兩個數進行比較,從而確定好后綴)
13     {
14         k--;                                                 
15     }
16     Suff[i] = i-k;                                           //其中i-k為最右邊下標,數組中的下標為i,，i代表子串中與最好后綴匹配的位置
17     if(Suff[i] != 0)
18         Suff2[m-Suff[i]] = SubLen-1-i;                       //確定偏移量
19   }
20 
21  int *bmGs = new int[SubLen];                                //bmGs數組主要記錄當在i處（i處為壞字符），則需要移動的距離
22  for(int i=0;i<SubLen-1;++i)
23      bmGs[i] = SubLen;
24  bmGs[m-1] = 0;
25 
26  for(int i=SubLen-2;i >= 0;i--) 
27  {
28       if(Suff[m-1-Suff2[i+1]] !=0 && Suff[m-1-Suff2[i+1]]!=11)
29            
30           bmGs[i] = Suff2[i+1];                                                                 //移動距離S,當與好后綴匹配時,移動距離
31     
32       else 
33         {  
34 
35             for(int j=i+2;j<m;j++)
36                 if(Suff[m-1-Suff2[j]] == (m-j))                                                 //判斷與前綴是否匹配
37                 {    
38                     bmGs[i] = Suff2[j];                                                         //測算出偏移距離
39                     break;
40                 }
41            
42           
43          }
44  }

bmGs數組主要記錄當在i處（i處為壞字符），則需要移動的距離,；Suff2數組，下標表示i處出現壞字符時,，在字符串前部最靠近壞字符且與i以后好后綴匹配的字符串的具體位

移量。從而可以測算出具體前部匹配具體坐標,。

下面給出具體BM算法：

  1 //壞字符算法，主要用來在移動時找到最大位移S,壞字符即移動最大距離
  2 void BM_ErrorChar(int SubLen,int CharByte[256],const char *SubString)
  3 {
  4    //BM_ErrorChar(SubLen,ByteChar);
  5    for(int i=0; i<SubLen; ++i)                  //SubLen-1,不考慮最后一個數
  6       CharByte[SubString[i]] = SubLen-i;      //如果i最后一個為SubLen-1,，則最后一個距離根據計算,，需要-1
  7 
  8 }
  9 
 10 
 11 int BM(const char *Source,const char *SubString)                      //Source為主串，SubString為子串
 12 { 
 13   int SourceLen = strlen(Source);
 14   int SubLen = strlen(SubString);
 15   int m=SubLen;
 16   //壞字符數組 （其中ByteChar數組的下標為字符,，表示此字符出現最后一次離子串尾最近的距離）
 17   int ByteChar[256];                        //256是因為下標為字符，字符為ASCII碼,，8位,，總共有256種組合
 18   for(int i=0;i<256;++i)
 19       ByteChar[i] = SubLen;
 20 
 21   
 22   //int *bmBc = new int[SubLen];
 23   //for(int i=1;i<SubLen;i++)
 24 
 25 
 26   //好后綴數組（其中Suff數組n內數字主要表示好后綴的最右邊下標與最左邊之間的差值）
 27   //   i.  如果在P中位置t處已匹配部分P'在P中的某位置t'也出現，且位置t'的前一個字符與位置t的前一個字符不相同,，則將P右移使t'對應t方才的所在的位置,。 
 28 
 29   //  ii.  如果在P中任何位置已匹配部分P'都沒有再出現,，則找到與P'的后綴P''相同的P的最長前綴x，向右移動P,，使x對應方才P''后綴所在的位置,。
 30 
 31   
 32   
 33   int *Suff = new int[SubLen];
 34   Suff[SubLen-1] = SubLen;                                   //Suff數組主要記錄以數組內標號為子串中的距離
 35 
 36   int *Suff2 = new int[SubLen];                              //Suff2數組主要記錄下標為以i為首字母的字符后綴離最近的匹配字符串的距離
 37   for(int i=0;i<SubLen;i++)
 38   Suff2[i] = 0;                                              //初始化為0
 39 
 40   
 41  for(int i=SubLen-2;i>=0;i--)
 42   {
 43     int k=i;
 44     while(k>=0 && SubString[k] == SubString[SubLen-1-i+k])   //下標SubLen+k-1-i與k相對應(從后面兩個數進行比較,從而確定好后綴)
 45     {
 46         k--;                                                 
 47     }
 48     Suff[i] = i-k;                                           //其中i-k為最右邊下標,數組中的下標為i，i代表子串中與最好后綴匹配的位置
 49     if(Suff[i] != 0)
 50         Suff2[m-Suff[i]] = SubLen-1-i;                       //確定偏移量
 51   }
 52 
 53  int *bmGs = new int[SubLen];                                //bmGs數組主要記錄當在i處（i處為壞字符）,，則需要移動的距離
 54  for(int i=0;i<SubLen-1;++i)
 55      bmGs[i] = SubLen;
 56  bmGs[m-1] = 0;
 57 
 58  for(int i=SubLen-2;i >= 0;i--) 
 59  {
 60       if(Suff[m-1-Suff2[i+1]] !=0 && Suff[m-1-Suff2[i+1]]!=11)
 61            
 62           bmGs[i] = Suff2[i+1];                                                                 //移動距離S,當與好后綴匹配時,移動距離
 63     
 64       else 
 65         {  
 66 
 67             for(int j=i+2;j<m;j++)
 68                 if(Suff[m-1-Suff2[j]] == (m-j))                                                 //判斷與前綴是否匹配
 69                 {    
 70                     bmGs[i] = Suff2[j];                                                         //測算出偏移距離
 71                     break;
 72                 }
 73            
 74           
 75          }
 76  } 
 77 
 78 
 79 //開始BM算法
 80   //基于后綴回溯比較法
 81   int pSubLen  ,pSourLen =  SubLen;                          
 82   if(SubLen==0)
 83       return -1;
 84   while(pSourLen<=SourceLen)                                               //主串是否到了盡頭             
 85   { 
 86       pSubLen = SubLen;                                                    //初始化
 87       while(SubString[--pSubLen]==Source[--pSourLen])                      //進行匹配比較
 88     {
 89 
 90        if(pSourLen < 0)  return -1;                                         //如果pSour,以子串長度為一組的主串掃描結束
 91            
 92        if(pSubLen == 0) return  pSourLen;                                   //為0,匹配成功
 93 
 94     }
 95     BM_ErrorChar(pSubLen,ByteChar,SubString);                                           //計算字符偏移量
 96     int CharLen = ByteChar[Source[pSourLen]];                                           //進行壞字符算法計算CharLen;
 97     int SuffLength = bmGs[pSubLen] ;                                                    //進行最好后綴法計算出來的偏移長度
 98     int MaxLen = MAX(CharLen, SuffLength);                                              //最后后綴算法,，分情況討論
 99         pSourLen += (SubLen-pSubLen);
100         pSourLen += MaxLen>1 ? MaxLen:1 ;                                               //進行偏移,pSour值進行恢復與回溯,SubArry - pSub為以前減去的值補回
101     
102   }
103   
104   return -1;
105 
106 }

測試結果：

char *T ="cddcdepcdedefgbcde"; //T為主串
char *S = "cdedefgbcde" ; //S為子串

在T[7]處開始匹配。

引用請注明出處：http://www.cnblogs.com/Su-30MKK/archive/2012/09/17/2688122.html

本站是提供個人知識管理的網絡存儲空間,，所有內容均由用戶發(fā)布,，不代表本站觀點。請注意甄別內容中的聯系方式,、誘導購買等信息,，謹防詐騙。如發(fā)現有害或侵權內容,，請點擊一鍵舉報,。

久久国产成人av_抖音国产毛片_a片网站免费观看_A片无码播放手机在线观看,色五月在线观看,亚洲精品m在线观看,女人自慰的免费网址,悠悠在线观看精品视频,一级日本片免费的,亚洲精品久,国产精品成人久久久久久久

關于字符串匹配算法研究