国外网站建设素材库,廊坊网站建设制作,系统做网站的地方,合肥公司网站开发实验七 字符串实验报告
一、实验目的与要求
1#xff09;巩固对串的理解#xff1b;
2#xff09;掌握串的基本操作实现#xff1b;
3#xff09;掌握 BF 和 KMP 算法思想。
二、实验内容
1. 给定一个字符串ababcabcdabcde和一个子串abcd,查找字串是否在主串中出现。…实验七 字符串实验报告
一、实验目的与要求
1巩固对串的理解
2掌握串的基本操作实现
3掌握 BF 和 KMP 算法思想。
二、实验内容
1. 给定一个字符串ababcabcdabcde和一个子串abcd,查找字串是否在主串中出现。出现就返回主串中的第一个匹配下标没有则返回-1。本题采用BF串匹配算法。
2.编写一个函数,计算一个子串在一个主串中出现的次数,如果该子串不出现,则返回0。本题考虑子串重叠,如:子串为aa,主串为aaa,考虑子串重叠结果为2,不考虑子串重叠结果为1。
示列1输入ababab,abababab 返回值2
示列2输入abab,abacabab 返回值1
提示
首先进行特殊情况判断如果模式串长度大于主串或者主串为空返回0。
然后分别遍历主串和模式串只要当前字符相等模式串和主串均后移一位如果不相等模式串重新回退到索引0的位置。
当模式串索引达到长度m时说明全部匹配上了。此时将匹配次数加一同时主串索引i回退到上次匹配开头的下一位模式串索引j回到0。
采用kmp算法
三、实验结果
1请将调试通过的运行结果截图粘贴在下面并说明测试用例和运行过程简述算法思想。
2请将源代码cpp文件和实验报告一起压缩上传。 实验1
运行结果 算法思想
BF算法的思想主要如下在主串和子串中设置比较的下标i和j本段代码中初始化均为0。循环比较直到主串中所剩字符个数小于子串的长度或者是子串的所有字符均比较完。如果主串A和子串B满足A[i]B[i]那么继续比较子串和主串的下一个字符否则将i和j回溯准备下一趟的比较。如果子串中的所有字符均比较完那么说明匹配成功返回匹配的起始比较下标否则说明匹配失败按照题目要求返回-1。
实验代码
#include iostream#include cstdio#include cstringusing namespace std;//BF串匹配算法int bf(char *strA, char *strB){//strA是主串strB是子串int i0,j0;int lenastrlen(strA);//主串的长度int lenbstrlen(strB);//子串的长度while(ilena jlenb){if(strA[i]strB[j]){i;j;}else{ii-j1;//如果i、j初始值为1则返回ii-j2j0;//重置子串的标记位置j}}//跳出循环遍历完成//判断字串情况if(jlenb){return i-j1;//成功匹配}return -1;//不成功匹配}//主函数-调试int main() {//int mybfbf(ababcabcdabcde,abcd);char strA[1000],strB[1000];//max长度设置为1000cout请输入主串endl;cinstrA;cout请输入子串endl;cinstrB;int mybfbf(strA,strB);if(mybf0){cout主串中的第一个匹配下标mybfendl;}else{coutmybfendl;}return 0;} 实验2
运行结果 算法思想
KMP算法的思想主要如下在主串A和子串B中设置比较的下标i和j本段代码中初始化均为0。循环比较直到主串中所剩字符个数小于子串的长度或者是子串的所有字符均比较完。如果A[i]B[j]或j0那么继续比较A和B的下一个字符否则将j向右滑动到next[i]的位置j next[i]准备下一趟的比较。如果子串中的所有字符均比较完那么说明匹配成功返回匹配的起始比较下标否则说明匹配失败按照题目的要求返回0。
实验代码
#include cstdio
#include cstring
#include iostream
using namespace std;int next[100];//全局数组变量 //获取next数组
void getNext(char b[],int next[]){int lenstrlen(b);next[0]-1;int k-1;int j0;while(jlen){if(k-1 || b[k]b[j]){j;k;next[j] k;}else{knext[k];}}
}//KMP算法
int kmp(char *a,char *b){int lenastrlen(a);int lenbstrlen(b);int i0,n0,k0;//n作为计数器 while(ilena){if(k-1 || a[i]b[k]){i;k;}else{knext[k];}if(klenb){n;knext[k];}}return n;
}int main(){char a[100000],b[10000];//a为主串b为子串 cout请输入主串endl; cina;cout请输入子串endl; cinb;getNext(b,next);cout子串出现次数为kmp(a,b);return 0;
}其他
#includeiostream
using namespace std;struct String{char *elem;int length;
};void Strcpy(String S,const char str[]){//忌引用数组 ,const!!!int i0;int str_len0;while(str[i]!\0){str_len;i;}//字符串长度 if(!str_len) S.length0;int k1,j0;S.elemnew char[str_len1];while(kstr_len)S.elem[k]str[j];S.elem[0] ;//0号位随意 S.lengthstr_len;
}int StrIndex_BF(String S,String T,int pos){int ipos,j1;while((iS.length)(jT.length)){//while((iS.length-T.length1)(jT.length))错误 if(S.elem[i]T.elem[j]){i;j;}else{ii-j2;//回溯操作 j1;if(iS.length-T.length1)break;//S中剩下元素小于T的元素个数 }}if(jT.length)//T中全部字符均匹配成功 return (i-T.length);elsereturn -1;
}void Destroy(String S){delete []S.elem;
}int main(){String S,T;
// Strcpy(S,ababcabcdabcde);//主串
// Strcpy(T,abcd);//模式串Strcpy(S,ababcabcacbab);//主串 Strcpy(T,abcac);//模式串 int pStrIndex_BF(S,T,1);//匹配函数 if(p!-1)cout匹配成功主串中的第一个匹配下标为pendl;elsecout匹配失败endl;Destroy(S);Destroy(T);return 0;
}#includeiostream
using namespace std;struct String{char* elem;int length;
};void StrCopy(String s,char a[]){int i0;int strlen0;while(a[i]!\0){strlen;i;}s.elemnew char[strlen1];int k1,j0;while(jstrlen)s.elem[k]a[j];s.elem[0]\0;s.lengthstrlen;
}void Get_next(String T,int (next)[20]){int i0,j1;next[1]0;while(jT.length){if(i0||T.elem[i]T.elem[j]){i;j;next[j]i;}elseinext[i];}
}int Strmatch_KMP(String S,String T,int next[]){int i1,j1,num0;if(S.lengthT.length)return 0;while((iS.length)(jT.length)){//while((iS.length-T.length1)(jT.length))错误 if(j0||(S.elem[i]T.elem[j])){i;j;}else jnext[j];if(jT.length){num;ii-j2;j1;//回溯if(iS.length-T.length1)break;//S中剩下元素小于T的元素个数 }}return num;
}void Destroy(String S){delete []S.elem;
}int main(){char a[20],b[20];gets(a);gets(b);String S,T;StrCopy(S,a);StrCopy(T,b);int next[20]{0,0,1};//初始化next【i】 Get_next(T,next);//找到对应的k值 int numStrmatch_KMP(S,T,next);//重叠次数 if(!num) cout子串不在主串中出现endl;else cout子串在主串中出现且重叠结果为numendl;Destroy(S);Destroy(T);return 0;
}
