2023年7月20日发(作者：)

实验项目一 串匹配问题

1. 实验题目

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

2. 实验目的

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

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

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

3. 实验要求

（1） 实现BF算法；

（2） 实现BF算法的改进算法：KMP算法和BM算法；

（3） 对上述三个算法进行时间复杂性分析，并设计实验程序验证分析结果。

4. 实验提示

BF算法，KMP算法和BM算法都是串匹配问题中的经典算法，BF算法和KMP算法请参见本章第3.2节。下面介绍BM算法。

BM算法是Boyer和Moore共同设计的快速匹配算法。BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比较顺序改为从左到右，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。

5. 实验代码

BF算法代码

#include

#include

#define N 50

void main()

{

char a[N],b[N];

printf("请输入待匹配的两个字符串，主串a为:n");

gets(a);

printf("模式串b为:n");

gets(b);

int i=1,j=1,s,t;

s=strlen(a);

t=strlen(b);

while(i

if(a[i]==b[j]){

i++;

j++;

}

else{

i=i-j+2;

j=1;

}

} if(j>=t)

printf("从a串的%d个字符开始匹配n",i-j+1);

else

printf("匹配失败n");

}

KMP算法代码

#include

#include

#define N 50

void GetNext(char t[],int next[])

{

next[1]=0;

int j=1,k=0,h;

h=strlen(t);

while(j

if((k==0)||(t[j]==t[k]))

{

j++;

k++;

next[j]=k;break;

}

else

k=next[k];

}

void main(){

char s[N],t[N];

int next[N]={0};

printf("请输入主串s:n");

gets(s);

printf("请输入模式串t:n");

gets(t);

int i=1,j=1,k=strlen(s)-1,h=strlen(t)-1;

while((i<=k)&&(j<=h))

{

if(s[i]==t[j]){

i++;

j++;

}

else{

GetNext(t,next);

j=next[j];

{if(j==0)

{ i++;

j++;

}

}

}

}

if(j>h)

printf("匹配的起始下表为:%dn",i-j+1);

else

printf("匹配失败n");

}

BM算法代码

#include

#include

#define N 50

int GetDist(char t[],char c){

int i,k=0;

int m;

m=strlen(t)-1;

for(i=m;i>0;i--){

if(t[i]==c){

k=i;break;

}

}

if((k!=m)&&(k!=0))

return m-k;

else

return m;

}

int BM(char s[],char t[],int n,int m){

int i,j;

i=m;

while(i<=n){

j=m;

while(j>0&&(s[i]==t[j])){

j=j-1;

i=i-1;

}

if(j==0){

return i+1;

break;

} else{

i+=GetDist(t,s[i]);

}

}

return 0;

}

void main(){

char s[N],t[N];

int r,n,m;

printf("请输入主串s:n");

gets(s);

printf("请输入模式串t:n");

gets(t);

n=strlen(s)-1;

m=strlen(t)-1;

r=BM(s,t,n,m);

if(r!=0)

printf("匹配的起始下标为:%dn",r);

else

printf("匹配失败");

}

6. 实验结果

BF算法实验结果

KMP算法实验结果 BM算法实验结果

时间复杂度分析

算法

BF

KMP

BM

7. 试验心得

时间复杂度

O（n*m）

O（n）

O（n/3）

、