串匹配实验报告
- 格式:doc
- 大小:66.00 KB
- 文档页数:6
实验成绩
华中师范大学计算机科学系
实验报告书
实验项目:串匹配问题
课程名称:算法分析与设计
班级: 1
实验时间:周六早上8:30-11:30
实验目的:一、深刻理解并掌握蛮力法的设计思想。
二、提高应用蛮力法设计算法的技能。
三、理解这样一个观点:用蛮力法设计的算法,一般来说,经过适
当的努力之后,都可以对算法的第一个版本进行一定程度的改
良,改进其时间性能。
实验报告要求:1、实现BF算法。
2、实现BF的改进算法:KMP算法。
3、对上述算法进行时间复杂性分析,并设计实验程序,分析结果。
BF算法内容:
#include
#include
using namespace std;
#define M 80
#define N 50
void main()
{
char S[M],T[N];
int i,j,count=0;
cout<<"请输入长串S:";
gets(S);
cout<<"请输入子串T:";
gets(T);
i=0;j=0;
while(count!=strlen(T)&&i<(strlen(S)))
{
int k=i;
if(S[i]==T[j])
{i++;j++,count++;}
else
{i=k+1;j=0;count=0;}
}
if(count==strlen(T))
{
cout<<"子串从长串的第"< 功!"< // break; } if(count!=strlen(T)) cout<<"字符串匹配失败!"< } 此算法的时间复杂度为O(M*N); 结果一:成功匹配 结果二:匹配失败 经改进后的KMP算法内容: # include # include using namespace std; #define M 80 #define N 50 void getnext(char *t,int *next) { int k = -1,j = 0; next[0] = -1; next[1] = 0; while(j < strlen(t)) { if((k == -1) || (t[j] == t[k])) { j++; k++; next[j]=k; } else { k = next[k]; } } } void main() { int i,j,count=0; char S[M],T[N]; cout<<"请输入长串S:"; cin>>S; cout<<"请输入子串T:"; cin>>T; int n = strlen(T); int *next = new int[n]; getnext(T,next); for(i=0,j=0;i { if((j == 0)||(S[i] == T[j])) { i++; j++; } else { j = next[j]; } } if(j==strlen(T)) cout<<"子串从长串的第"< else cout<<"字符串匹配失败!"< } 此算法的时间复杂度为O(N); 若匹配成功,结果如下: 若字符串S和T不匹配,结果如下: 问题分析:通过两种算法的比较,主要区别在于next数组的加入,我通过上网查询以及参考书本上next数组的求解方法,得出此KMP算法,语法上无任何错误,经多次修改,得此算法。注意next数组与j衔接以防出错。