蛮力算法 串匹配.docx

蛮力算法 串匹配.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）。

且在实际应用中因为效率的原因可能不能派上用场，但是还是不能忽略它。

正如书中作者所说，在解决小规模问题的时候也不失为一个方法，而且也是更复杂算法的基础。

通过本次上机实验对课本上程序段的完善调试，不仅对蛮力算法有了深入的了解，同时也很好的复习了以前学过的Ｃ、和Ｃ＋＋两门编程语言，很感谢这次实验中老师的指导和同学的帮助，让我在算法设计与分析的学习中获益良多。