算法——字符串匹配之朴素算法

╰+攻爆jí腚メ 2022-08-13 00:47 195阅读 0赞

## 前言 ##

本文介绍的是字符串匹配最简单的算法--朴素字符串匹配算法。该算法的原理非常简单，就是通过一个循环找到所有有效偏移，即对[![0 \\leqslant s < n-m+1][0 _leqslant s _ n-m_1]][0 _leqslant s _ n-m_1_0 _leqslant s _ n-m_1]检查是否满足条件[![P\[1..m\]=T\[s+1..s+m\]][P_1..m_T_s_1..s_m]][P_1..m_T_s_1..s_m_P_1..m_T_s_1..s_m]。算法没有进行预处理，只是对其进行匹配处理，算法过程中是每次移动一位的比较字符，所以时间复杂度是非常大O((n-m+1)m)。

## 算法实现 ##

根据该算法的描述，这里给出算法导论中的伪代码，并根据伪代码给出具体实现代码，从代码中很清晰地看到该算法的时间复杂度。注：字符下标是从0开始的。

**伪代码：**

NAIVE_STPRING_MATCHER(T,P)
    	n = T.length;
    	m = P.length;
    	for(s=0;s <= n-m;s++)
    		if P[1..m]==T[s+1..s+m];
    			print "Pattern occurs with shift" s;

**C++源码实现：**

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int NAIVE_STPRING_MATCHER(const string &T,const string &P);
    
    
    int main()
    {
    	string T = "abcdefghijk";
    	string P = "defg";
    
    	int s = NAIVE_STPRING_MATCHER(T,P);
    	if(s>=0)
    		cout<<"Pattern occurs with shift:"<<s<<endl;
    	else 
    		cout<<"Not macth the P in the T. "<<endl;
    
    	system("pause");
    	return 0;
    }
    
    int NAIVE_STPRING_MATCHER(const string &T,const string &P)
    {
    	int n = T.length();
    	int m = P.length();
    	
    	if(n < m) return -1;
    	int s_length = n-m;
    
    	for (int s = 0; s <= s_length; s++)
    	{
    		bool flag = false;
    		for(int i = 0;i < m;i++)
    		{
    			if(T[s+i]==P[i])
    				flag = true;
    			else 
    			{
    				flag = false;
    				break;
    			}
    		}
    
    		if(flag)
    			return s;
    	}
    	return -1;
    }

注意：以上的C++源码只可以找出字符串中一次匹配，例如T=abcdefghijkdefg，P=defg，则只能找出第一个有效偏移s=3，第二个有效偏移s=11不能找出。

为了能够找出所有匹配项，我们可以在第一次匹配成功后，继续移动整个模式串，把所有匹配成功的位置找出来。只需要对上面的源码进行修改即可，源码如下：

#include <iostream>
    #include <string>
    
    using namespace std;
    
    void NAIVE_STPRING_MATCHER(const string &T,const string &P);
    
    
    int main()
    {
    	string T = "abcdefghijkdefg";
    	string P = "defg";
    
    	 NAIVE_STPRING_MATCHER(T,P);
    	system("pause");
    	return 0;
    }
    
    void NAIVE_STPRING_MATCHER(const string &T,const string &P)
    {
    	int n = T.length();
    	int m = P.length();
    	
    	if(n < m) cout<<"the length of P larger than T";
    	int s_length = n-m;
    
    	for (int s = 0; s <= s_length; s++)
    	{
    		bool flag = false;
    		for(int i = 0;i < m;i++)
    		{
    			if(T[s+i]==P[i])
    				flag = true;
    			else 
    			{
    				flag = false;
    				break;
    			}
    		}
    
    		if(flag)
    			cout<<"match successed, the s is:"<<s<<endl;
    	}
    }

或者：

#include <iostream>
    #include <string>
    
    using namespace std;
    
    void NAIVE_STPRING_MATCHER(const string &T,const string &P);
    
    
    int main()
    {
    	string T = "abcdefghijkdefg";
    	string P = "defg";
    
    	NAIVE_STPRING_MATCHER(T,P);
    	system("pause");
    	return 0;
    }
    
    void NAIVE_STPRING_MATCHER(const string &T,const string &P)
    {
        int M = P.length();
        int N = T.length();
      
        for (int s = 0; s <= N - M; s++)
        {
            int j;  
            for (j = 0; j < M; j++)
                if (T[s+j] != P[j])
                    break;
            if (j == M)  
               cout<<"Pattern found at index:"<<s<<endl;
        }
    }

参考资料：

《算法导论》

[0 _leqslant s _ n-m_1]: http://latex.codecogs.com/gif.latex?0&space;\leqslant&space;s&space;<&space;n-m+1
[0 _leqslant s _ n-m_1_0 _leqslant s _ n-m_1]: http://private.codecogs.com/eqnedit.php?latex=0&space;\leqslant&space;s&space;<&space;n-m+1
[P_1..m_T_s_1..s_m]: http://latex.codecogs.com/gif.latex?P[1..m]=T[s+1..s+m]
[P_1..m_T_s_1..s_m_P_1..m_T_s_1..s_m]: http://private.codecogs.com/eqnedit.php?latex=P[1..m]=T[s+1..s+m]