【算法设计与分析】实验1：字符串匹配问题的算法设计与求解

一、实验目的

二、实验环境

三、实验内容

四、核心代码

五、记录与处理

六、思考与总结

七、完整报告和成果文件提取链接

一、实验目的

给定一个文本，在该文本中查找并定位任意给定字符串。

1、深刻理解并掌握蛮力法的设计思想；

2、提高应用蛮力法设计算法的技能；

3、理解观点：用蛮力法设计算法策略，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。

二、实验环境

1、机房电脑 Window7

2、Eclipse/DEVC++等

三、实验内容

1、针对给定两组字符串，分别利用BF算法及KMP算法开展问题分析、建模、算法设计与优化；

(1)问题分析：

当给出两组字符串，主串s，子串t，要想找到子串t在主串s中的位置，常规时我们用肉眼可以一眼看出，但当字符串非常多时，问题就变得复杂了，用代码思想解决问题时，我们最容易想到暴力匹配BF算法。

为了避免BF算法多次回溯的缺点，我们要尽量减少回溯的次数。

而KMP算法则提出了采用相等前后缀来解决BF算法多次回溯的缺点。比如：

根据KMP算法的思想，两个字符串拥有相同部分的前后缀，所以只用移动一部分就可以了

求出其最长相等前后缀是关键，根据此数组存储数值——表示该处字符不匹配时应该回溯到的字符下标

求出子串的next数组：

在下面情况时，a与c不匹配：

将子串的指针移动到下标为2的字符下。

假设主串长度为m，子串长度为n ，KMP算法的时间复杂度为O(m+n)，BF算法的空间复杂度为O(n)，与BF算法相比，算法效率提高了很多。

(2)算法改进

而对于KMP算法，还有需要改进的地方，根据nextval的值，我们很容易就知道回溯后的字符与原字符是否相同，这样就减少了原KMP算法中，部分重复回溯的过程。

对上述算法进行时间复杂性分析，并输出程序运行时间及运行结果。

最好情况下，时间复杂度为O(n)；全部遍历完时的最差时间复杂度为O(m*n)，算法空间复杂度为O(1)，BF算法耗时间不耗费空间。KMP算法的时间复杂度为O(m+n)，空间复杂度为O(n)，与BF算法相比，算法效率提高了很多。

四、核心代码

int BF(SqString s,SqString t)            //BF算法 
{
	int i=0,j=0;
	while(i<s.length&&j<t.length)		
	{
		if(s.data[i]==t.data[j])		
		{
			i++;						
			j++;
		}
		else
		{
			i=i-j+1;					
			j=0;						
		}
	}
	if(j>=t.length) 					
	    return(i-t.length);		
	else
	    return(-1);
}

void GetNext(SqString t,int next[])    //求子串t的next数组，进行代码优化
{
	int j,k;							
	j=0;k=-1;
	next[0]=-1;							
	while(j<t.length-1)					
	{									
		if(k==-1||t.data[j]==t.data[k])		
		{
			j++;k++;
			next[j]=k;						
		}
		else k=next[k];						
	}										
}

int KMPIndex(SqString s,SqString t)       //KMP算法
{
	int next[MaxSize],i=0,j=0;
	GetNext(t,next);
	while(i<s.length&&j<t.length)
	{
		if(j==-1||s.data[i]==t.data[j])   
		{								  
			i++;
			j++;
		}
		else j=next[j];
	}
	if(j>=t.length)
	    return(i-t.length);
	else
	    return(-1);
}

void GetNextval(SqString t,int nextval[])  //求模式串t的nextval数组，进行KMP的代码优化
{
	int j=0,k=-1;							
	nextval[0]=-1;							
	while(j<t.length-1)
	{
		if(k==-1||t.data[j]==t.data[k])		
		{									
			j++;k++;						
			if(t.data[j]!=t.data[k])		
			   nextval[j]=k;
			else
			   nextval[j]=nextval[k];		
		}
		else k=nextval[k];
	}
}