《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法） |
您所在的位置：网站首页 › deepl9bb鏓bf › 《数据结构》实验报告四：串的模式匹配（BF算法、KMP算法） |
《数据结构》实验报告四：串的模式匹配（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 #include #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;ilength && ilength;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 s1s->length-start+1) sub->length = 0; else { for(i=0;idata[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;ilength){ 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;ilength || 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(ilength && jlength) { 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 %d\n",index_bf(&s,&t,k)); getNext(&t,next); getNextVAL(&t,nextval); printf("KMP:\n"); printf(" next[]:"); for(i=0;i |
【本文地址】