《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法）
一、实验目的
1、了解串的基本概念。
2、掌握串的模式匹配算法的实现 。
二、实验预习
说明以下概念
1、模式匹配：
串的模式匹配就是子串的定位运算。
设有两个字符串 S 和 T ，S为主串(正文串)，T为子串(模式串)。在主串S中查找与模式串T相匹配的子串，若匹配成功，确定相匹配的子串中的第一个字符主串S中出现的位置。
2、BF算法：
即暴力破解算法(Brute Force)，属于模式匹配算法中的一种。
算法思想：从主串和模式串的第一个字符开始比较，匹配成功则进行下一字符的比较；匹配失败则主串比较的字符回溯到初始比较字符的下一位，而模式串比较的字符回溯到模式串第一个字符，接着继续进行字符比较。
3、KMP算法：
KMP算法也属于模式匹配算法的一种，是一种改进后的匹配算法。
KMP算法的改进在于当出现字符不匹配时，主串比较的字符无需回溯，而模式串则利用已经匹配成功的部分字符，确定模式串回溯的位置（无需回溯到第一个字符）。
KMP算法减少了模式串与主串的匹配次数，达到快速匹配的目的。
三、实验内容和要求
！注 ！
本实验中的字符数组 data 从下标为0的数组分量开始存储字符串。部分教材为便于说明问题，字符串从下标为1的数组分量开始存储，下标为0的分量闲置不用，故代码略有区别。
1、阅读并运行下面程序，根据输入写出运行结果。
#include<stdio.h>
#include<string.h>
#define MAXSIZE 100 //串的最大长度
typedef struct{
char data[MAXSIZE]; //存储串的一维数组（从下标为0的数组分量开始存储字符串）
int length; //串的当前长度
}SqString;
int strCompare(SqString *s1,SqString *s2); /*串的比较*/
void show_strCompare();
void strSub(SqString *s,int start,int sublen,SqString *sub); /*求子串*/
void show_subString();
int strCompare(SqString *s1,SqString *s2){
int i;
for(i=0;i<s1->length && i<s2->length;i++)
if(s1->data[i] != s2->data[i])
return s1->data[i] - s2->data[i];
//字符比较完成，还需比较字符串长度
return s1->length - s2->length;
/* s1=s2,返回值=0
s1>s2,返回值>0
s1<s2,返回值<0 */
}
void show_strCompare(){
SqString s1,s2;
int k;
printf("n***show Compare***n");
printf("input string s1:");
gets(s1.data);
s1.length=strlen(s1.data);
printf("input string s2:");
gets(s2.data);
s2.length=strlen(s2.data);
if((k=strCompare(&s1,&s2))==0)
printf("s1=s2n");
else if(k<0)
printf("s1<s2n");
else
printf("s1>s2n");
printf("n***show over***n");
}
void strSub(SqString *s,int start,int sublen,SqString *sub){
int i;
if(start<1 || start>s->length || sublen>s->length-start+1)
sub->length = 0;
else
{
for(i=0;i<sublen;i++)
sub->data[i]=s->data[start+i-1];
sub->length=sublen;
}
}
void show_subString(){
SqString s,sub;
int start,sublen,i;
printf("n***show subString***n");
printf("input string s:");
gets(s.data);
s.length=strlen(s.data);
printf("input start:");
scanf("%d",&start);
printf("input sublen:");
scanf("%d",&sublen);
strSub(&s,start,sublen,&sub);
if(sub.length==0)
printf("ERROR!n");
else{
printf("subString is:");
for(i=0;i<sublen;i++)
printf("%c",sub.data[i]);
}
printf("n***show over***n");
}
int main(){
int n;
do{
printf("n---String---n");
printf("1. strComparen");
printf("2. subStringn");
printf("0. EXITn");
printf("ninput choice:");
scanf("%d",&n);
getchar();
switch(n){
case 1:
show_strCompare();
break;
case 2:
show_subString();
break;
default:
n=0;
break;
}
}while(n);
return 0;
}
输入：
1
student
students
2
Computer Data Stuctures
10
4
运行结果：
2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。
#include<stdio.h>
#include<string.h>
#define MAXSIZE 100 //串的最大长度
typedef struct{
char data[MAXSIZE]; //存储串的一维数组（从下标为0的数组分量开始存储字符串）
int length; //串的当前长度
}SqString;
int index_bf(SqString *s,SqString *t,int start); /*模式匹配-BF算法*/
void getNext(SqString *t,int next[]); /*计算目标串的next数组*/
int index_kmp(SqString *s,SqString *t,int start,int next[]); /*模式匹配-KMP算法*/
void show_index();
int index_bf(SqString *s,SqString *t,int start){
//补充代码
}
void getNext(SqString *t,int next[]){ /*计算模式串t的next数组*/
int i=0;
int j=-1;
next[0]=-1;
while(i < t->length){
if(-1==j || (t->data[i]==t->data[j]))
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int index_kmp(SqString *s,SqString *t,int start,int next[]){
//补充代码
}
void show_index(){
SqString s,t;
int k;
int i;
int next[MAXSIZE]={0};
int nextval[MAXSIZE]={0};
printf("n***show index***n");
printf("input string s:");
gets(s.data);
s.length=strlen(s.data);
printf("input string t:");
gets(t.data);
t.length=strlen(t.data);
printf("input start position(1≤start position≤%d):",s.length);
scanf("%d",&k);
printf("BF:nthe result of BF is %dn",index_bf(&s,&t,k));
getNext(&t,next);
printf("KMP:n");
printf("next[]:");
for(i=0;i<t.length;i++)
printf("%3d",next[i]);
printf("n");
printf("the result of KMP is %dn",index_kmp(&s,&t,k,next));
printf("n***show over***n");
}
int main(){
show_index();
return 0;
}
BF算法代码：
int index_bf(SqString *s,SqString *t,int start){ /*返回模式串t在主串s中第start个字符开始第一次出现的位置;若不存在,返回0*/
//模式串t长度为0 或 起始查找位置超出主串范围:直接返回0
if(0 == t->length || start < 1 || start > s->length)
return (0);
int pos=start-1; //pos记录主串s开始匹配的字符下标
int i=pos; //i指向主串s当前正待比较的字符下标
int j=0; //j指向模式串t当前正待比较的字符下标
while( i < s->length && j < t->length )
{
if(s->data[i] == t->data[j]) //匹配成功:i,j都++,继续比较后续字符
{
i++;
j++;
}
else //匹配失败
{
pos++; //主串开始匹配的位置+1
i=pos; //i回溯到主串初始位置下一字符
j=0; //j回溯到模式串第一个字符
}
}
if(j >= t->length)
return (pos-start+2); //返回模式串t在主串s中第start个字符开始第一次出现的位置
else
return (-1); //查找失败,返回-1
}/*index_bf*/KMP算法代码：
int index_kmp(SqString *s,SqString *t,int start,int next[]){ /*返回模式串t在主串s中第start个字符开始第一次出现的位置;若不存在,返回0*/
//模式串t长度为0 或 起始位置超出主串范围:直接返回0
if(0 == t->length || start < 1 || start > s->length)
return (0);
int i=start-1; //i指向主串s当前正待比较的字符下标
int j=0; //j指向模式串t当前正待比较的字符下标
while(i<s->length && j<t->length)
{
if(-1 == j || (s->data[i] == t->data[j]))
{
i++;
j++;
}
else //匹配失败
{
j=next[j]; //i不回溯,j回溯到next[j]
}
}
if(j>=t->length)
return (i-j-start+2); //返回模式串t在主串s中第start个字符开始第一次出现的位置
else
return (-1); //查找失败,返回-1
}/*index_kmp*/输入：
abcaabbabcabaacbacba
abcabaa
1
运行结果：
3、在第2题的基础上，对next数组进行改进，实现计算目标串的nextval数组的算法，并进行验证。
nextval数组算法代码：
void getNextVAL(SqString *t,int nextval[]){ /*计算模式串t的nextval数组*/
int i=0;
int j=-1;
nextval[0]=-1;
while(i < t->length){
if(-1 == j || (t->data[i]==t->data[j]))
{
i++;
j++;
if(t->data[i] != t->data[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}/*getNextVAL*/show_index函数补充代码：
void show_index(){
SqString s,t;
int k;
int i;
int next[MAXSIZE]={0};
int nextval[MAXSIZE]={0};
printf("n***show index***n");
printf("input string s:");
gets(s.data);
s.length=strlen(s.data);
printf("input string t:");
gets(t.data);
t.length=strlen(t.data);
printf("input start position(1≤start position≤%d):",s.length);
scanf("%d",&k);
printf("BF:nthe result of BF is %dn",index_bf(&s,&t,k));
getNext(&t,next);
getNextVAL(&t,nextval);
printf("KMP:n");
printf(" next[]:");
for(i=0;i<t.length;i++)
printf("%3d",next[i]);
printf("n");
printf("nextval[]:");
for(i=0;i<t.length;i++)
printf("%3d",nextval[i]);
printf("n");
printf("the result of KMP is %dn",index_kmp(&s,&t,k,nextval));
printf("n***show over***n");
}输入：
abcaabbabcabaacbacba
abcabaa
1
运行结果：