实用标准文档
文案大全 实验报告一 串匹配问题
班级：_计算机师 _ 学 号： 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→i
i 0→b i→a S[a]=T[b]且b≠n a加1 b加1 b=n Y N Y Y Y N N N BF算法 结开主串S长度→m 0→a 0→b a≦S[a]=T[b]且b≠n a加1 b加1 b=n Y Y Y N N N KMP算法 结next[b]→b a-b→a b=-1 b加1 实用标准文档 文案大全 开i≦主串S长模式T长j≧0且S[i]=T[j] i减1 j减1 j<0 Y Y Y N N N BM算法 结0→a 0→b 0→z 模式T长i+DIST(T,S实用标准文档 文案大全 五、实验结果与结论：（给出测试数据以及程序运行结果，并进行比较，得出自己的结论） 设计思想：设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。 BE算法： #include #include #include main() { char s[100]; char t[100]; int i,a,b,m,n; printf("*****please input a string:"); scanf("%s",s); printf("please input search string:"); scanf("%s",t); m=strlen(s); n=strlen(t); printf("*******BF********\n"); for(i=0;i { b=0; a=i; while(s[a]==t[b]&&b!=n) { a++; b++; } if(b==n) 实用标准文档 文案大全 { printf("success!\n"); return 0; } } printf("no found!:%s\n\n",&t); return 0; } KMP算法： #include #include #include main() { char s[100]; char t[100]; 实用标准文档 文案大全 int i,a,b,m,n; printf("*****please input a string:"); scanf("%s",s); printf("please input search string:"); 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"); return 0; } else { b=b+1; a=a-b; } if(b=-1) {b++;} else return 0; 实用标准文档 文案大全 } printf("no found!:%s\n\n",&t); return 0; } BM算法： #include using namespace std; #include #include static int time=0; //dist函数 int dist(char ch,char *T) { int k=-1,t1; 实用标准文档 文案大全 t1=strlen(T); for(int i=0;i { if(ch==T[i]&&i k=i+1; if(ch==T[i]&&i==t1-1) k=0; } if(k==-1) k=0; return t1-k; } void BM(char *S,char *T) { int s1,t1; s1=strlen(S); t1=strlen(T); int j,i=t1-1; while(i { j=t1-1; while(j>=0&&S[i]==T[j]) { i--; j--; 实用标准文档 文案大全 } if(j==-1) { cout<<"该串从第&i位开始匹配："< break; } else { time++; i=i+dist(S[i],T); } } if(i>=s1) cout<<"匹配不成功"< } void main() { int *next=new int;//给next指针分配空间 char *S=new char;//给S指针分配空间 char *T=new char;//给T指针分配空间 cout<<"请输入串S:"; cin>>S; cout<<"请输入串T:"; cin>>T; cout<<"BM算法: "; BM(S,T); cout<<"一共执行循环"< } 实用标准文档 文案大全 实验心得： 蛮力法的算法设计，BF算法的思想最简单，但是比较刻板。升级版的KMP和BM算法设计起来有一点难度，但是它们的思想要巧妙一点。