蛮力算法 串匹配.docx
- 文档编号:15775016
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:10
- 大小:55.08KB
蛮力算法 串匹配.docx
《蛮力算法 串匹配.docx》由会员分享,可在线阅读,更多相关《蛮力算法 串匹配.docx(10页珍藏版)》请在冰点文库上搜索。
蛮力算法串匹配
1、实验题目
给定一个文本,在该文本中查找并定位任意给定的字符串。
2、实验目的
(1)深刻理解并掌握蛮力算法的设计思想;
(2)提高蛮力法设计算法的技能;
(3)理解观点:
算法逐个版本进行改良,改进其时间性能。
3、实验要求
(1)实现BF算法;
(2)实现BF算法的改进算法:
KMP算法和BM算法;
(3)对上述算法进行时间复杂性分析,并设计实验程序验证
分析结果。
4、算法的设计思想
(1)BF算法:
①在串S、T中比较的起始下标为i和j;
②循环直到S中剩下的字符个数小于T的长度或T的所有
字符都比较完:
如果S[i]=T[j],则继续比较S和T的下一个字符,否则
将i和j回溯,进行下一趟比较;
③如果T中的字符都比较完,则匹配成功,返回匹配的起
始下标,否则匹配失败,返回0。
(2)KMP算法:
①在串S、T中比较的起始下标为i和j;
②循环直到S中剩下的字符个数小于T的长度或T的所有
字符都比较完:
如果S[i]=T[j],则继续比较S和T的下一个字符,否则
将i向右滑动到next[j]的位置,即j=next[i];
如果j=0,则将i和j分别加1,准备进行下一趟比较;
③如果T中的字符都比较完,则匹配成功,返回匹配的起
始下标,否则匹配失败,返回0。
(3)BM算法:
假设将主串中自位置i起往左的一个子串与模式串进行从
右到左的匹配过程中,若发现不匹配,则下次应从i+dist
(si)的位置开始进行下一次匹配,其效果相当于模式和
主串都向右滑动一段距离dist(si),即跳过dist(si)
个字符无需进行比较。
二、代码和运行结果截图
1、代码
#include
#include
usingnamespacestd;
classstringcom
{
private:
chars[256],t[256];//分别代表主串与要匹配的串
intnum,pos[256];//分别记录匹配次数与所出现匹配的位置
intnext[256],dist[256];//KMP,BM记录的不匹配时下一位置
FILE*fp1,*fp2;
public:
voidfile();
voidBF();
voidKMP();
voidBM();
voidGetNext();
voidGetDist();
//voidInput()
//{cin>>s>>t;}
voidOutput();
};
voidmain()
{
stringcomstr;
str.file();//可以选择从文件读取字符串
//cout<<"请输入主串S,和子串t:
"< //str.Input();//这里选择输入字符串 str.BF(); str.KMP(); str.BM(); } /**********读文件信息**************/ voidstringcom: : file() { if((fp1=fopen("s.txt","r"))==NULL)//从文件中读入 { cout<<"错误! 请将源程序存入s.txt"< } else fgets(s,256,fp1); if((fp2=fopen("t.txt","r"))==NULL)//从文件中读入 { cout<<"错误! 请将源程序存入t.txt"< } else fgets(t,256,fp2); } /***************BF******************/ voidstringcom: : BF() { inti,j=0; num=0; for(i=0;i if(s[i]==t[j]) { j++; if(! t[j]) { pos[num]=i-j+2; num++; i=i-strlen(t)+1;//i从下一个位置开始,避免了重叠的串 j=0; } } else { i=i-j; j=0; } cout< "< Output(); } /***************KMP******************/ voidstringcom: : KMP() { inti,j; num=0; i=0; j=0; GetNext(); while(strlen(s)-i>0) if(j==0||(s[i]==t[j])) { i++;j++; if(! t[j]) { pos[num]=i-strlen(t)+1;//位置从1开始记录,下标从0开始 i=pos[num];//i从下一个位置开始,避免了重叠的串 num++; j=0; } } elsej=next[j]; cout< "< Output(); } /***********GetNext******************/ voidstringcom: : GetNext() { intj,k; next[1]=0; j=1; k=0; while(j if(k==0||(t[j]==t[k])) { j++; k++; next[j]=k; } elsek=next[k]; } /************BM**********************/ voidstringcom: : BM() { inti,j,len; num=0; len=strlen(t); i=len-1; GetDist(); while(i { j=len-1; while(j>=0&&s[i]==t[j]) { i--; j--; } if(j==-1) { pos[num++]=i+2; i+=strlen(t)+1;//i从下一个位置开始,避免了重叠的串 } elsei+=dist[s[i]]; } cout< "< Output(); } /***********GetDist***************/ voidstringcom: : GetDist() { inti,lenth; lenth=strlen(t); for(i=0;i<256;i++) dist[i]=lenth; for(i=0;i dist[t[i]]=lenth-i-1; dist[t[lenth-1]]=lenth; } /***************输出*****************/ voidstringcom: : Output() { inti; if(num) { cout<<"主串中共有"< cout<<"位置是: "; for(i=0;i cout<<"["< cout< } elsecout<<"无相匹配的串! "< } 2、截图 (1)主串和模式串分别从s.txt和t.txt中读入 s.tx: ccccccccaaaacccccccccccaaaaaaaabbbbbbbbbbbb t.txt: aaaaaabbbbb (2)主串和模式串从键盘读入 三、实验结果分析 蛮力算法也称穷举法,是一种简单而直接的解决问题的方法,直接基于问题的描述,但蛮力算法设计的算法其时间性能很低。 BF算法: 一般情况下m《n,最坏情况下的时间复杂度是O(n*m);KMP算法: 时间复杂度是O(n+m),当m《n时的时间复杂度是O(n);BM算法: 当m《n时的时间复杂度是O(n)。 且在实际应用中因为效率的原因可能不能派上用场,但是还是不能忽略它。 正如书中作者所说,在解决小规模问题的时候也不失为一个方法,而且也是更复杂算法的基础。 通过本次上机实验对课本上程序段的完善调试,不仅对蛮力算法有了深入的了解,同时也很好的复习了以前学过的C、和C++两门编程语言,很感谢这次实验中老师的指导和同学的帮助,让我在算法设计与分析的学习中获益良多。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 蛮力算法 串匹配 算法 匹配