实验报告一串匹配问题? 班级：_计算机师_学号：2 姓名：_ 一、实验题目：给定一个文本,在该文本中查找并定位任意给定字符串 二、实验目的： (1)深刻理解并掌握蛮力法的设计思想; (2)提高应用蛮力法设计算法的技能; (3)理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对算法的第一个版本进行一定程度的改良,改进其时间性能 三、实验要求： (1)实现 BF 算法; (2)实现 BF 算法的改进算法:KMP 算法和 BM 算法; (3)对上述 3 个算法进行时间复杂性分析,并设计实验程序验证分析结果 四、算法描述（对算法主要部分进行伪代码描述或画出流程图） BF 算法： 基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；若不相等，则从主串S的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T，匹配失败这个算法称为朴素的模式匹配算法，简称 BF 算法 KMP 算法： 基本思想： 1.在串 S 和串 T 中分别设比较的起始下标 i 和 j； 2.循环直到 S 中所剩字符长度小于 T 的长度或 T 中所有字符均比较完毕 2.1 如果 S[i]=T[j]，则继续比较 S 和 T 的下一个字符；否则 2.2 将 j 向右滑动到 next[j]位置，即 j=next[j]； 2.3 如果 j=0，则将 i 和 j 分别加 1，准备下一趟比较； 2.4 如果 T 中所有字符均比较完毕，则返回匹配的起始下标；否则返回0； BM 算法： 基本思想：BM 算法与 KMP 算法的主要区别是匹配操作的方向不同。
虽然BM 算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式 T 右移的计算方法却发生了较大的变化 ?? 开主串 S 长模式 T 长0→ii #include #include main() { chars[100]; chart[100]; inti,a,b,m,n; printf("*****pleaseinputastring:"); scanf("%s",s); printf("pleaseinputsearchstring:"); scanf("%s",t); m=strlen(s); n=strlen(t); printf("*******BF********\n"); for(i=0;i #include #include main() { chars[100]; chart[100]; inti,a,b,m,n; printf("*****pleaseinputastring:"); scanf("%s",s); printf("pleaseinputsearchstring:"); scanf("%s",t); m=strlen(s); n=strlen(t); printf("*******KMP********\n"); for(a=0;a<=m-n;a++) { b=0; while(s[a]==t[b]&&b!=n) { a++; b++; } if(b==n) { printf("success!\n"); return0; } else { b=b+1; a=a-b; } if(b=-1) {b++;} elsereturn0; } printf("nofound!:%s\n\n",&t); return0; } ?BM 算法： #include usingnamespacestd; #include #include staticinttime=0; //dist 函数 intdist(charch,char*T) { intk=-1,t1; t1=strlen(T); for(inti=0;i=0&&S[i]==T[j]) { i--; j--; } if(j==-1) { cout<<"该串从第&i 位开始匹配："<=s1) cout<<"匹配不成功"<>S; cout<<"请输入串 T:"; cin>>T; cout<<"BM 算法:"; BM(S,T); cout<<"一共执行循环"<
升级版的 KMP 和 BM 算法设计起来有一点难度，但是它们的思想要巧妙一点。
