算法系列笔记9(字符串匹配)

冷不防 2022-08-07 05:35 77阅读 0赞

字符串匹配指有一个文本串S和一个模式串P,现在要查找P在S中的位置。

**主要有以下算法：**

![Center][]

其中朴素算法和KMP算法我们在这边blog[http://blog.csdn.net/lu597203933/article/details/41124815][http_blog.csdn.net_lu597203933_article_details_41124815]中已经讲解过。RP算法时间复杂度较高，我也没看，想看可以看算法导论。这里主要讲解有限自动机的字符串匹配算法。

**有限自动机的定义：**

![Center 1][]

有限自动机字符串匹配主要是构建一个状态转移函数。&(q,a)表示状态q<其中状态q表示已经匹配成功q个字符了>接收字符a后的状态，就等于Pqa(接收成功的q个字符连接上a)后缀的最长P前缀的长度。

例子：

![Center 2][]

伪代码：

![Center 3][]

![Center 4][]![Center 5][]

代码如下：

#include <iostream>
    #include <string>
    using namespace std;
    #define MAXSIZE 10
    int transitionArray[MAXSIZE][MAXSIZE];
    
    void computingTransition(const string &p, const string &alpha){
    
    	for(int q = 0; q < p.size(); q++){   // 初始状态q = 0
    		for(int i = 0; i < alpha.size(); i++){   // 所拥有的字母表
    			int k = q+1;
    			string s = p.substr(0, q)+ alpha[i];
    			bool flag = false;
    			for(; k > 0 && !flag; k--){
    				int j = 0;
    				for( ;j < k; j++){
    					if(p[j] != s[s.size()-k+j])break;
    				}
    				if(j == k) flag= true;
    			}
    			if(flag) transitionArray[q][i] = ++k;
    			else transitionArray[q][i] = 0;
    			cout << transitionArray[q][i] << " ";
    		}
    		cout << endl;
    	}
    
    }
    
    void finiteAutomationStringMatch(const string &s, int m){
    	int q = 0;
    	int i = 0;
    	for(int i = 0; i < s.size(); i++){
    		q =  transitionArray[q][s[i]-97];
    		if(q == m){
    			cout << "YES" << endl;
    			cout << i-m+1 << endl;
    			break;
    		}
    	}
    	if(i == s.size())
    		cout << "NO" << endl;
    
    }
    
    int main(){
    	string s("abababacaba"), p("ababaca");
    	string alpha = "abc";
    	computingTransition(p, alpha);
    	finiteAutomationStringMatch(s, p.size());
    	return 0;
    }

结果：

![Center 6][]

[Center]: /images/20220805/051b3b76c39047289b085dd58d286362.png
[http_blog.csdn.net_lu597203933_article_details_41124815]: http://blog.csdn.net/lu597203933/article/details/41124815
[Center 1]: /images/20220805/5fe69832362944bbaf2837c8f0e6b3ae.png
[Center 2]: /images/20220805/525c8959f73a4268baa68458f60e2b90.png
[Center 3]: /images/20220805/4152fc4c6fb74ac8a4a9f310df79960b.png
[Center 4]: https://img-blog.csdn.net/20150313200026738?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTHU1OTcyMDM5MzM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: /images/20220805/33f4201c74a346bcae02db65e172344d.png
[Center 6]: /images/20220805/bbf18154ddf248bfa96e3fa202b1be29.png