零零散散学算法之再叙字符串匹配

出自：http://blog.csdn.net/fengchaokobe/article/details/8919074

       字符串匹配问题这是个老话题了，而我们也热衷于学习和探讨这个问题，并且我们也经常会用到它。比如说，我们用vim打开一个文本文件，要在这个文件中查找某一个字符串时，我们只需在底行模式下输入/String即可；再比如，在linux终端中，我们要把当前目录下所有的c文件打印出来，那么这时候我们就会利用正则表达式来进行匹配操作(所有的c文件可表示为*.c)，而不是挨个去找。

 

好了，书接正文。写本篇文章的目的有二：

 

       其一：先前也写过字符串匹配的文章，不过那篇文章只说了字符串固定匹配以及KMP算法，没有对字符串动态匹配进行讲述。所以一直想写关于动态匹配的文章；

       其二：对于一个算法爱好者，如一位仁兄所说：Say what you think and show your code！如若这样，岂不快哉！

 

第一章 固定串匹配

 

       我为什么叫它固定串呢？我还是举个例子说明一下吧(没办法，语言表达能力不好啊)！假设有源字符串…superfcing…，我们想知道子串superfc是否在源串中出现过？此时不难看出子串是一个确定的字符串(不含有不确定的字符)，那么我就将它成为固定字符串匹配法。

 

       解决这种情况的算法不用我多说，自然是KMP算法(最坏情况为O(strlen(source_string) + k))了。对于这个算法先前也说过，在这就不细说了。这个算法的关键步骤就是源串前缀数组的生成。下面我用图例给出前缀数组的生成过程：

 

 

       对于KMP算法，归总起来就是：扫描源字符串，更新并标记子串在源串中出现的位置。

 

       附注：关于KMP算法的前缀函数，当数组的起始下标为0时，务必不要让前缀函数的初值设为0，如果这样的话，可能会死循环。你如果对此有兴趣，自己可以试试。

 

好了，固定串匹配的情况就是这样，解决方法也有了，接下来我们看看代码的实现：

 

代码中使用到的变量代表的含义：

[html] view plaincopyprint?
 
  1. /*  Source:源串  
  2. **  SourceLength:源串长度  
  3. **  Prefix:前缀数组  
  4. **  Pattern:匹配串，即子串  
  5. **  P_Length:子串长度  
  6. **  Buffer:当源串中有子串匹配时，用Buffer保存这些子串  
  7. */<span style="font-size:18px;"></span>  
[cpp] view plaincopyprint?
 
  1. /**为KMP算法得到前缀数组**/  
  2. void GetPrefixArray(char *Source, int *Prefix, int SourceLength)  
  3. {  
  4.     int k = 0, i;  
  5.     Prefix[k] = -1;//当下标起始为0时，起始值务必设为1(原因见如下解释)  
  6.   
  7.     for(i = 1; i < SourceLength; i++)  
  8.     {  
  9.         while(Source[k] != Source[i]  &&  k > 0)  
  10.         {  
  11.             k = Prefix[k];  
  12.         }  
  13.         if(Source[k] == Source[i])  
  14.         {  
  15.             ++k;  
  16.         }  
  17.         Prefix[i] = k;  
  18.     }  
  19. }  
[cpp] view plaincopyprint?
 
  1. void StringMatchOfKMP(char *Source, int SourceLength, int *Prefix,  
  2.             char *Pattern, int P_Length, char *Buffer)  
  3. {  
  4.     int i = 0, j = 0, index = 0;  
  5.   
  6.     GetPrefixArray(Source, Prefix, SourceLength);  
  7.   
  8.     while(i < SourceLength)  
  9.     {  
  10.         while(j > 0 && Source[i] != Pattern[j])  
  11.         {  
  12.             j = Prefix[j];  
  13.         }  
  14.         if(Source[i] == Pattern[j])  
  15.         {  
  16.             j++;  
  17.         }  
  18.   
  19.         if(j == P_Length)  
  20.         {  
  21.             memcpy((Buffer + index * P_Length), Pattern, strlen(Pattern));  
  22.             index++;//当有多个匹配时，index * P_Length为每个子串在Buffer中的起始位置  
  23.         }  
  24.         i++;  
  25.     }  
  26. }  

 第二章 单字符动态匹配

 

       所谓单字符动态匹配，就是：当字串中出现？字符时，该字符表示匹配任意的一个字符(因为它是任意的一个字符，所以说它是单字符动态匹配)。那么这种情况怎么解决呢？很简单，我们只需要对源串做一次遍历，并不需要像固定串匹配那样利用KMP算法。即子串在匹配源串的过程中，当遇见？字符时，我们直接认为子串中的该字符和源串中对应位置的字符匹配成功。举个例子，假设源串为helloSuperfc，子串为S*per，那么当源串和子串中的S匹配时，分别做++，这个时候源串中的u就会和子串中的*相比较，此时我们就认为*就是字符u，匹配成功，然后进行下一个字符的匹配。

 

好，给个图示：

 

      单字符动态匹配就是这样，我们来看看它的实现代码：

[cpp] view plaincopyprint?
 
  1. void StringMatchOfAsk(char *Source, int SourceLength, char *Pattern,  
  2.                         int P_Length, char *Buffer)  
  3. {  
  4.     int i = 0, j = 0;  
  5.     int index = 0;  
  6.     while(i < SourceLength)  
  7.     {  
  8.         if((Pattern[j] == Source[i]) || (Pattern[j] == '?'))  
  9.         {  
  10.             /*匹配完成*/  
  11.             if((j + 1) == P_Length)  
  12.             {  
  13.                 memcpy((Buffer + index * P_Length), (Source + i - P_Length + 1), P_Length);  
  14.                 index++;  
  15.                 j = 0;  
  16.             }  
  17.             else  
  18.             {  
  19.                 j++;  
  20.                 i++;  
  21.             }  
  22.         }  
  23.         else  
  24.         {  
  25.             i = i - j + 1;//相当于i++  
  26.             j = 0;  
  27.         }  
  28.     }  
  29. }  


第三章 多字符动态匹配

 

       所谓多字符动态匹配，就是：当子串中出现*字符时，该字符表示可以匹配至少0个以上的字符(因为它可以匹配多个字符，所以说它是多字符动态匹配)。那么这种情况怎么解决呢？我认为它比单字符动态匹配还要简单，即当子串中的*与源串中的对应字符比较时，我就认为*字符包含从源串中的当前位置开始，直到当子串中的下一个字符与源串中的字符相等时，匹配结束。这么说太拗口了，我用一个图例来说明一下：

 

我们来看看代码的实现：

[cpp] view plaincopyprint?
 
  1. void StringMatchOfStar(char *Source, int SourceLength, char *Pattern,  
  2.                         int P_Length, char *Buffer)  
  3. {  
  4.     int i = 0, j = 0;  
  5.     int index = 0;  
  6.   
  7.     while(i < SourceLength)  
  8.     {  
  9.         if(Source[i] == Pattern[j])  
  10.         {  
  11.             /*匹配完成*/  
  12.             if(P_Length == ++j)  
  13.             {  
  14.                 memcpy(Buffer, (Source + index), i - index + 1);  
  15.                 break;  
  16.             }  
  17.   
  18.             /*保存起始匹配的下标*/  
  19.             if(0 == j - 1)  
  20.             {  
  21.                 index = i;  
  22.             }  
  23.         }  
  24.         else if(Pattern[j] == '*')  
  25.         {  
  26.             j++;  
  27.         }  
  28.         i++;  
  29.     }  
  30. }  

第四章 结束语

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/mfryf/p/3090247.html