• 热门专题

字符串匹配的算法(暴力算法和KMP算法)

作者:  发布日期:2015-04-21 20:50:30
Tag标签:算法  字符串  暴力  
  • 学习字符串匹配算法有一段时间了,不过还是有点迷糊,虽然了解算法过程,但是在编码的时候还是会有些迷糊。
    先把写的程序放在这里,以后有时间再来翻着看看吧!

    #include<iostream>
    #include<string>
    using namespace std;
    int KMPfind(char* s, char* p);
    void GetNext(char* p, int next[]);
    int ViolentMatch(char* s, char* p);
    int main()
    {
    	char s1[] = "abcaabbaacaadaabbaa";
    	char s2[] = "aadaab";
    	cout << "In the string " << s1 << ", the string " << s2 << " is started at the "
    		<< ViolentMatch(s1, s2);
    	cout << endl<<KMPfind(s1, s2)<<endl;
    	return 0;
    }
    void GetNext(char* p, int next[])
    {
    	int pLen = strlen(p);
    	int i = -1; int j = 0;//i从-1开始,让不匹配的回溯到开始位置进行匹配
    	next[0] = -1;//
    	for (; j < pLen-1;)
    	{
    		if (i==-1||p[i] == p[j])
    		{
    			++i; ++j; next[j] = i;
    		}
    		else
    			i = next[i];//i回溯到next[i]的位置
    	}
    	
    }
    int KMPfind(char* s, char* p)
    {
    	int i = 0;
    	int j = 0;
    	int sLen = strlen(s);
    	int pLen = strlen(p);
    	int * next = new int[strlen(p)];
    	GetNext( p,  next);
    	while (i < sLen && j < pLen)
    	{
    		//①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++      
    		if (j == -1 || s[i] == p[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			//②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]      
    			//即通过next数组得到下次比较的位置   
    			j = next[j];
    		}
    	}
    	delete []next;
    	if (j == pLen)//比较完毕而且比较了模式字符串的长度表示找到匹配字符串
    		return i - j;
    	else
    		return -1;
    }
    int ViolentMatch(char* s, char* p)
    {
    	int sLen = strlen(s);
    	int pLen = strlen(p);
    
    	int i = 0;
    	int j = 0;
    	while (i < sLen && j < pLen)
    	{
    		if (s[i] == p[j])
    		{
    			//①如果当前字符匹配成功(即S[i] == P[j]),则i++,j++      
    			i++;
    			j++;
    		}
    		else
    		{
    			//②如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0      
    			i = i - j + 1;
    			j = 0;
    		}
    	}
    	//匹配成功,返回模式串p在文本串s中的位置,否则返回-1  
    	if (j == pLen)
    		return i - j;
    	else
    		return -1;
    }
    

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规