《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了《数据结构》实验报告四：串的模式匹配（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=s2\n");
    else if(k<0)
        printf("s1<s2\n");
    else
        printf("s1>s2\n");
    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. strCompare\n");
        printf("2. subString\n");
        printf("0. EXIT\n");
        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;
}

输入：

student

students

Computer Data Stuctures

运行结果：

《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法）

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 %d\n",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 %d\n",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

运行结果：

《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法）

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 %d\n",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 %d\n",index_kmp(&s,&t,k,nextval));
	printf("\n***show over***\n");
}

输入：

abcaabbabcabaacbacba

abcabaa

运行结果：

《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法）文章来源地址https://www.toymoban.com/news/detail-428171.html