【数据结构】字符串-模式匹配BF算法（动态图解、c++、java）

【数据结构】字符串-模式匹配BF算法（动态图解、c++、java）

文章目录

什么是模式匹配？模式匹配 BF 算法步骤（动图）简单的匹配代码BF 算法复杂度分析总结

GitHub同步更新（已分类）：Data_Structure_And_Algorithm-Review（能给个star最好了！！！）

以下是本篇文章正文内容，下面案例可供参考。

---

什么是模式匹配？

字串的定位运算称为串的模式匹配 或串匹配 。

假设有两个串 S、T，设 S 为主串，也称正文串；T 为子串，也称模式。

在主串S中查找与模式T相匹配的子串，如果查找成功，返回匹配的子串第一个字符在主串中的位置。

最笨的办法就是穷举S的所有子串，判断是否与T匹配，该算法称为BF（Brute Force）算法。

模式匹配 BF 算法步骤（动图）

从 S 第0个字符开始，与T第0个字符比较。
如果相等，继续比较下一个字符，否则跳转向下一步；从 S 第1个字符开始，与T第0个字符比较。
如果相等，继续比较下一个字符，否则跳转向下一步；从 S 第2个字符开始，与T第0个字符比较。
如果相等，继续比较下一个字符，否则跳转向下一步；
…

如果 T 比较完毕，则返回 T 在 S 中第一个字符出现的索引（从零开始）；如果 S 比较完毕，则返回 -1，说明 T 在 S 中未出现。

设，S = “abcabdcababdcabeac”，T = “abdcabe”，求子串 T 在主串 S 中位置。

先来一遍文字说明，再上图解。

S[0] == T[0] , S[1] == T[1] , S[2] != T[2] , 跳转下一步；S[1] != T[0] , 跳转下一步；S[2] != T[0] , 跳转下一步；S[3] == T[0] , S[4] == T[1] , S[5] == T[2] , S[6] == T[3] , S[7] == T[4] , S[8] == T[5] , S[9] != T[6] 跳转下一步；S[4] != T[0] , 跳转下一步；S[5] != T[0] , 跳转下一步；S[6] != T[0] , 跳转下一步；S[7] == T[0] , S[8] == T[1] , S[9] != T[2] , 跳转下一步；S[8] != T[0] , 跳转下一步；S[9] == T[0] , S[10] == T[1] , S[11] == T[2] , S[12] == T[3] , S[13] == T[4] , S[14] == T[5] , S[15] == T[6] ；T 比较完毕，返回 9。

简单的匹配代码

从算法步骤部分不难看出：

i 的回退位置为 i - j + 1 。j 的回退位置为 0 。

c++代码如下（示例）：

int Index_BF(char *S,char *T){
    int i = 0,j = 0;
    while(i < strlen(S) && j < strlen(T)){
        if(S[i] == T[j]){
            i++,j++;
        }else{
            i = i - j + 1;
            j = 0;
        }
    }

    if(j == strlen(T)){
        return i - j;
    }
     return -1;
}

java代码如下（示例）：

public int index_BF(String s,String t){
    int i = 0,j = 0;
   	while(i 
BF 算法复杂度分析 
1. 最好情况： 
 
例如：S = “abcdefg” ，T = “def”。
 
此时，在匹配时，i 、j 都不需要回退。
 
平均时间复杂度为 
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         +
        
        
         m
        
        
         )
        
       
       
        O(n + m)
       
      
     O(n+m) 。
 
2. 最坏情况： 
 
例如：S = “aaaab” ，T = “ab”。
 
此时，在最后一次匹配前，i、j 一直在回退。
 
平均时间复杂度为  
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         ×
        
        
         m
        
        
         )
        
       
       
        O(n × m)
       
      
     O(n×m) 。
 
 
总结 
在示例比较时，有一步比较为：
 
 通过模式匹配BF算法，i、j 回退为：
 
 但通过观察，我们可以发现，我们完全可以直接这么比较：
 

 来达到，i 不回退，只 j 回退的目的，大大减少了时间复杂度。
 
此方法便是  KMP算法  。
 
 
虽然没人看，但还是想说一下：
 
本来打算明天发 KMP 的，但是有些事情需要处理一下，明天更不了 KMP 了 QAQ。
 
只能先发一篇存稿了，下下一篇绝对 KMP。
 
下期预告：数据的顺序存储
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5710245.html