算法分析--串匹配问题

《算法分析--串匹配问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、实验内容和目的实验内容：给定一个文本，在该文本中查找并定位任意给定的字符串。实验目的：(1)深刻理解并掌握蛮力法的设计思想；(2)提高应用蛮力法设计算法的技能；(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。实验要求：(1)实现BF算法；(2)实现BF算法的改进算法：KMP算法和EM算法；(3)对上述3个算法进行时间复杂性分析，并设计实验程序验证分析结果。二、所用仪器、材料(设备名称、型号、规格等)操作系统：MicrosoftWindows7开发平台：MicrosoftVisualStudio2010编程

2、语言：C语言三、实验方法、步骤登录MicrosoftWindows7操作系统T打开VisualStudio2010开发平台T新建“项目”T“Win32控制台应用程序”9输入项目名称弓“应用程序设置”T勾选“空项口”复选框T右击左侧“解决方案资源管理器”下的“源文件”T“添加”9“新建项…”T新建一个“C卄文件(・cpp)”T在新建的.cpp文件屮输入串匹配算法的程序代码9调试T运行T记录结果~＞完成实验报告。四、实验过程原始记录(数据、图表、计算等)源代码见实验报告所在目录下的BFFromFile.cpp、KMPFromFile.cpp、BMFromFile.cpp,以下是部分程序代码的截图

3、：BFFromFile.cpp：181Hintbf(chars[]rchart[]rincsLength^inctLength)182{183inti=0;/*s串的下标*/184intj=O;/*t串的下标★/185intsrart=0;/*s串中的起始比较下标*/186187/*以下whil己语句进行s和匸的匹配*/188while((sLength-start>=tLength)&&(匸[j]!=■■))189{190if(s[i]==t[j])/*in果匹配成功，进行下一个字符的匹配*/191{192i++；193j++；194continue;KMPFromFile.cpp:1

4、86Bintkrrip(chars[],chart[],intsLengthrinctLength)187{188intnext[LENGTH_T]={0};189190/*调用getNext函数为n亡x匸数组賦值*/191getNext(t,next);192193int1=0;/*s串的下标*/194intj=O;/*t串的下标*/195intstart=0;/*s串中的起始比较下标*/196197intk=0;/*用于镰f出格式的控制的附加变量*/198199/*以下whi1已语句进行s和匸的匹配*/200while((sLength-start>=tLength)&&(匸[j]!=，

5、，))BMFromFile.cpp：191Bintbm(chars[]fchart[]rintsLengthzinttLength)192{193inti=tLength-l;/串s的下标，从模式串的末尾开始匹配*/194intj=O;/*j表示模式串的下标*/195196mt)c=0;/*用于镭出格式的控制的附加变量”197198while(K=sLength)/*while1start*/199{200j=tLength-l;201while(j>=0&&s[i]==t[j])/*while2start*/202{203/*如果匹配成功，则继续向左匹配*/204五、实验结果在实现应用

6、三种串匹配算法在文件中查找指定字符串之前，先对每个算法的正确性进行验证。编写3个小的程序BF.cpp、KMP.cpp、BM.cpp（源代码文件与实验报告在同一口录下），应用这三个小程序，对教材中的例子进行跟踪演示如下：说明：MATCHED表示当前位置发生匹配；RECALL表示当前位置发生冋溯；i表示主串数组下标；j表示模式串数组下标（i,j均从1开始计算，但返冋匹配位置的下标值则从零开始计算）BF算法演示：特点：主串和模式串同时回溯KMP算法演示（回溯次数明显减少）:特点：主串不回溯SBC:Windowssystem32盍式吕:ababcabcacbab吕:abcacMATCHED：■1

7、1ababcabcacbab■J1aMATCHED：■12ababcabcacbab■J2abrecallJ■1■2ababcabcacbabJ0aMATCHED：■13ababcabcacbab■J1aMATCHED：■14ababcabcacbab■J2abMATCHED：■15ababcabcacbab■J3abcMATCHED：■16ababcabcacbab■J4abcarecallT]■16aba