字符串的模式匹配实验报告

8086汇编语言程序实验：实验二、字符串匹配实验题目：1、（必做题）编程实现：从键盘分别输入两个字符串（不必等长），然后进行比较，若两个字符串有相同的字符，则显示“MATCH”，若字符都不相同则显示“NO MATCH”。

2、（选做题）编程实现：从键盘分别输入两个字符串，然后进行比较，若两个字符串的长度和对应字符都完全相同，则显示“MATCH”，否则显示“NO MATCH”。

对应程序如下所示：;第1题;====================================HUICHE MACRO ;定义一个具有回车、换行功能的宏，为程序多次回车换行所调用。

MOV DL,0DH ;用2号功能“显示”回车。

MOV AH,02HINT 21HMOV DL,0AH ;用2号功能“显示”换行。

MOV AH,02HINT 21HENDMDA TA SEGMENTMESSAGE1 DB 'MATCH','$' ;定义“MATCH”提示信息，“$”作为调用9号功能的结束符。

MESSAGE2 DB 'NO MATCH','$' ;定义“NO MA TCH”提示信息。

TISHI1 DB 'Please input the first string:','$' ;提示输入第1个字符串的提示信息。

TISHI2 DB 'Please input the second string:','$' ;提示输入第1个字符串的提示信息。

STRING1 DB 100 ; 100为存第一个字符串的最大可用空间的字节数。

DB ? ;预留字节，存储将要输入的第1个字符串的实际长度。

DB 100 DUP(?) ;预留100个字节空间，用于存放第1个字符串。

STRING2 DB 100DB ?DB 100 DUP(?)DA TA ENDSSTACK SEGMENT ;定义一个50字节大小的堆栈段空间。

实验三串的模式匹配⼀、实验⽬的1、了解串的基本概念2、掌握串的模式匹配算法的实现⼆、实验预习说明以下概念1、模式匹配：数据结构中字符串的⼀种基本运算，给定⼀个⼦串，要求在某个字符串中找出与该⼦串相同的所有⼦串。

2、BF算法：BF算法，即暴⼒(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将⽬标串S的第⼀个字符与模式串T的第⼀个字符进⾏匹配，若相等，则继续⽐较S的第⼆个字符和 T的第⼆个字符；若不相等，则⽐较S的第⼆个字符和T的第⼀个字符，依次⽐较下去，直到得出最后的匹配结果。

BF算法是⼀种蛮⼒算法。

3、KMP算法：KMP算法是⼀种改进的字符串匹配算法，KMP算法的核⼼是利⽤匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的⽬的。

具体实现就是通过⼀个next()函数实现，函数本⾝包含了模式串的局部匹配信息。

三、实验内容和要求1、阅读并运⾏下⾯程序，根据输⼊写出运⾏结果。

#include<stdio.h>#include<string.h>#define MAXSIZE 100typedef struct{char data[MAXSIZE];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;}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");elseprintf("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;}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;}运⾏程序输⼊：1studentstudents2Computer Data Stuctures104运⾏结果：2、实现串的模式匹配算法。

实验四：KMP算法实验报告一、问题描述模式匹配两个串。

二、设计思想这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。

注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：int Index(String S,String T,int pos)//参考《数据结构》中的程序{i=pos;j=1;//这里的串的第1个元素下标是1while(i<=S.Length && j<=T.Length){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}//**************(1)}if(j>T.Length) return i-T.Length;//匹配成功else return 0;}匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子：S:aaaaabababcaaa T:ababcaaaaabababcaaaababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babc)如果不回溯就是aaaaabababcaaaaba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaaababc这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。

如果T为a bcdef这样的，大没有回溯的必要。

改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。

如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：...ababd...ababc->ababc这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。

竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告篇一：串的模式匹配算法串的匹配算法——bruteForce(bF)算法匹配模式的定义设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。

通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。

模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。

bF算法brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。

以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。

实现代码如下：/*返回子串T在主串s中第pos个字符之后的位置。

若不存在，则函数返回值为0./*T非空。

intindex(strings,stringT,intpos){inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1；}if(j>T[0])returni-T[0];elsereturn0;}}bF算法的时间复杂度若n为主串长度，m为子串长度则最好的情况是：一配就中，只比较了m次。

最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m).篇二：数据结构实验报告-串实验四串【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：bF和Kmp。

3、了解串的应用。

【实验学时】2学时【实验预习】回答以下问题：1、串和子串的定义串的定义：串是由零个或多个任意字符组成的有限序列。

实验6 字符串匹配实验目的：掌握字符串的查找与匹配的有关算法。

掌握串指令的使用方法，数据段、附件段的设置，源串、目的串地址指针的设置与使用，CMPS与REPE（REPNE）的使用技巧实验要求：写一个算法计算和显示一个字符串SUBSTR在字符串STR出现的位置与次数。

层次要求如下：C．在数据区的字节变量中有一个字符串STR，输出字符串“CS”在STR 中第一次出现位置（用16进制）。

如果STR中不包含“CS”则显示“No match!”；B．键盘输入一个以回车结尾的字符串，并把结果存放于数据区的具有80字节的变量STR中，输出字符串“CS”在STR中第一次出现位置（用16进制）。

如果STR中不包含“CS”则显示“No match!”；A．键盘输入一个以回车结尾的字符串，并把串存放于数据区的具有80字节的变量STR中；再输入一个关键词，存入具有8个字节的变量SUBSTR中。

输出字符串SUBSTR在STR中第一次出现位置（用10进制）。

如果STR中不包含SUBSTR的内容则显示“No match!”。

注：对有潜力的同学，输出子字符串在STR中出现的次数。

实验结果：层次C：如STR为“Computer Science-CS, Shanghai Univ.”，则输出12H如STR为“Computer Science, Shanghai Univ.”，则输出No match!层次B：如键盘输入“Computer Science-CS, Shanghai Univ.”，回车，则输出12H如键盘输入“Computer Science, Shanghai Univ.”，回车，则输出No match!层次A：结果如下Please input a string and press Enter key when you want to stop!School:CSE-Computer Engineering and Science回车Please input a keyword:CES回车8对另一个输入结果Please input a string and press Enter key when you want to stop!School:CSE-Computer Engineering and Science回车Please input a keyword:CST回车No match!实验报告要求:1、分析要点及调试后的正确程序。

试验四课程名称实验室名称实验名称字符串的模式匹配实现指导教师成绩1、实验目的字符串的模式匹配实现2、实验原理和内容能够使用标志变量去实现程序的某种功能的判定，充分利用while循环语句实现模式匹配并能判定模式匹配是否成功.3、实验步骤1.数据结构类型的定义2.编写insert函数寻找字符串p在字符串t中首次出现的起始位置，定义一个标志变量suc，判断匹配是否成功，若成功，返回起始位置，否则返回-13.编写主函数，将字符串p和字符串t的长度先赋值给p.length和t.length，打印输出所需查找的模式串在主串中的起始位置4、程序及运行结果（或实验数据记录及分析）#include<stdio.h>#define maxsize 100typedef struct{char str[maxsize];int length ;}seqstring;int index(seqstring p, seqstring t){int i,j, suc;i=0; suc=0;while((i<=t.length-p.length) && (!suc)){j=0 ; suc=1;while ((j<=p.length-1) && suc)if (p.str[j]==t.str[i+j] ) j++;elsesuc=0;++i;}if (suc) return (i-1);else return (-1);}main(){seqstring t, p;int sum;printf("请输入主串t:");scanf("%s",t.str);t.length=strlen(t.str);printf("请输入所需查找的子串p:");scanf("%s",p.str);p.length=strlen(p.str);sum=index(p,t);printf("\n");if (sum==-1) printf("no found");elseprintf("所需查找子串第一次出现的位置是：%d",sum+1); }在屏幕上输出的结果：。

一、实验目的1. 理解串匹配算法的基本原理和实现方法。

2. 掌握KMP算法和朴素算法的原理和实现过程。

3. 通过实验对比分析两种算法的性能，验证算法的效率和适用场景。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发工具：PyCharm三、实验内容1. 串匹配算法的原理介绍2. 朴素算法的实现与测试3. KMP算法的实现与测试4. 两种算法的性能对比四、实验步骤1. 串匹配算法的原理介绍串匹配算法是指在一个文本串中查找一个模式串的位置。

常用的串匹配算法有朴素算法和KMP算法。

（1）朴素算法（Brute-Force算法）：通过逐个字符比较主串和待匹配串，如果匹配成功，则返回匹配位置；如果匹配失败，则回溯到主串上的一个新位置，并在待匹配串上从头开始比较。

（2）KMP算法：通过构建一个部分匹配表（next数组），记录模式串中每个位置对应的最长相同前缀后缀的长度。

在匹配过程中，当出现不匹配时，通过查阅next数组确定子串指针回退位置，从而避免重复比较。

2. 朴素算法的实现与测试（1）实现朴素算法```pythondef brute_force_search(text, pattern):n = len(text)m = len(pattern)for i in range(n - m + 1):j = 0while j < m:if text[i + j] != pattern[j]:breakj += 1if j == m:return ireturn -1```（2）测试朴素算法```pythontext = "ABABDABACDABABCABAB"pattern = "ABABCABAB"print(brute_force_search(text, pattern)) # 输出：10 ```3. KMP算法的实现与测试（1）实现KMP算法```pythondef kmp_search(text, pattern):def build_next(pattern):next_array = [0] len(pattern)k = 0for i in range(1, len(pattern)):while k > 0 and pattern[k] != pattern[i]: k = next_array[k - 1]if pattern[k] == pattern[i]:k += 1next_array[i] = kreturn next_arrayn = len(text)m = len(pattern)next_array = build_next(pattern)k = 0for i in range(n):while k > 0 and text[i] != pattern[k]:k = next_array[k - 1]if text[i] == pattern[k]:k += 1if k == m:return i - m + 1return -1```（2）测试KMP算法```pythontext = "ABABDABACDABABCABAB"pattern = "ABABCABAB"print(kmp_search(text, pattern)) # 输出：10```4. 两种算法的性能对比为了对比两种算法的性能，我们分别测试了不同的文本串和模式串长度，并记录了运行时间。

微机原理实验字符串匹配实验一、实验目的（1）掌握提示信息的使用方法及键盘输入信息的方法。

（2）进一步熟悉在PC机上建立、汇编、连接、调试和运行汇编语言程序的过程。

二、实验要求根据提示信息，从键盘输入两个字符串，实现两个字符串的比较。

如两个字符串中有一个字符相同，则显示“MATCH”，否则显示“NO MA TCH”.三、实验程序框图本实验程序如图所示：Array四、参考程序CRLF MACROMOV AH ,02HMOV DL,0DHINT 21HMOV AH,02HMOV DL,0AHINT 21HENDMDATA SEGMENTMESS1 DB’MATCH’,0DH,0AH,’$’MESS2 DB’NO MA TCH’,0DH,0AH,’MAXLEN1 DB 81ACTLEN1 DB ?STRING1 DB 81 DUP(?)MAXLEN2 DB 81ACTLEN2 DB?STRING2 DB 81 DUP(?)DATA ENDSSTACK SEGMENT STACKSTA DB 50 DUP(?)TOP EQU LENGTH STASTACK ENDSCODE SEGMENTASSUME CS: CODE,DS:DA TA,ES:DATA,SS:STACK START: MOV AX,DA TAMOV DS,AXMOV ES,AXMOV AX,STACKMOV SS,AXMOV SP,TOPMOV AH,09HMOV DX,OFFSET MESS3INT 21HCRLFMOV AH,0AHMOV DX,OFFSET MAXLEN1INT 21HCRLFMOV AH,09HMOV DX,OFFSET MESS4INT 21HMOV AX,0AHMOV DX,OFFSET MAXLEN2INT 21HCRLFCLDMOV SI,OFFSET STRING1MOV CL,[SI-1]MOV CH,00HKKK: MOV DI,OFFSET STRING2 PUSH CXMOV CL,[DI-1]MOV CH,00HMOV AL,[SI]MOV DX,DIREPNZ SCASBJZ GGGINC SIPOP CXLOOP KKKMOV AH,09HMOV DX,OFFSET MESS2INT 21HJMP PPPGGG: MOV AH,09HMOV DX,OFFSET MESS1INT 21HPPP: MOV AX,4C00HINT 21HCODE ENDSEND START。

太原理工大学现代科技学院课程实验报告专业班级学号姓名指导教师一、实验目的掌握提示信息的使用方法及键盘输入信息的用法。

二、实验内容1、编写程序,实现两个字符串比较。

如果两个字符串中有一个字符相同,显示“MATCH”,否则,显示“NO MATCH”。

2、程序框图三、所用仪器与软件仪器:电脑一台软件:Masm for Windows 集成实验环境 2009、7四、实验方法、步骤1、编写程序代码2、运行程序,修改错误代码3、再次运行代码直至运行出正确结果五、源码程序编制及分析注释CRLF MACRO 宏定义MOV AH,02H AH=02HMOV DL,0DH DL=0DHINT 21H 系统功能调用,输出回车字符MOV AH,02H AH=02HMOV DL,0AH DL=0AINT 21H 系统功能调用,输出换行符ENDM 宏定义结束DATA SEGMENT 定义数据段MESS1 DB 'MATCH',0DH,0AH,'$' 定义8个数据储存单元MESS2 DB 'NO MATCH',0DH,0AH,'$' 定义11个数据储存单元MESS3 DB 'INPUT STRING1:',0DH,0AH,'$' 定义17个数据储存单元MESS4 DB 'INPUT STRING2:',0DH,0AH,'$' 定义17个数据储存单元MAXLEN1 DB 81 定义最大长度为81个字节ACTLEN1 DB ?STRING1 DB 81 DUP (?) 定义STRING1长度为81 MAXLEN2 DB 81 定义最大长度为81ACTLEN2 DB ?STRING2 DB 81 DUP (?) 定义STRING2长度为81DATA ENDS 数据段结束STACK SEGMENT STACK 定义堆栈段STA DB 50 DUP (?) 定义50个数据储存单元TOP EQU LENGTH STA 给TOP赋值50STACK ENDS 堆栈段结束CODE SEGMENT 定义代码段ASSUME CS:CODE,DS:DATA,ES:DATA,SS:STACK 定义段基址START: MOV AX,DATAMOV DS,AX 把DATA的首地址赋给DSMOV ES,AX 把DATA的首地址赋给ESMOV AX,STACKMOV SS,AX 把STACK的首地址赋给SSMOV SP,TOP 给SP赋值50MOV AH,09H AH=09HMOV DX,OFFSET MESS3 把MESS3的偏移地址赋给DXINT 21H 系统功能调用MOV AH,0AH AH=0AHMOV DX,OFFSET MAXLEN1 把MAXLEN1的偏移地址赋给DXINT 21H 系统功能调用CRLFMOV AH,09H AH=09HMOV DX,OFFSET MESS4 把MESS4的偏移地址赋给DXINT 21H 系统功能调用MOV AH,0AH AH=0AHMOV DX,OFFSET MAXLEN2 把MAXLEN2的偏移地址赋给DXINT 21H 系统功能调用CRLFCLDMOV SI,OFFSET STRING1 把STRING1的偏移地址赋给SIMOV CL,[SI-1] 把SI-1内的内容赋给CLMOV CH,00H CH=00HKKK: MOV DI,OFFSET STRING2 把STRING2的偏移地址赋给DI PUSH CX 将CX压入堆栈MOV CL,[DI-1] 将DI-1内的的内容赋给CLMOV CH,00H CH=00HMOV AL,[SI] 将SI内的内容赋给ALMOV DX,DI 将DI赋给DXREPNZ SCASB 寻找第一个相同字符JZ GGG ZF=0执行GGG否则顺序执行INC SI SI自加1POP CX 弹出CXLOOP KKK 跳转到KKK循环MOV AH,09HMOV DX,OFFSET MESS2INT 21H 系统功能调用JMP PPP 跳转到PPPGGG: MOV AH,09HMOV DX,OFFSET MESS1INT 21H 输出MESS1PPP: MOV AX,4C00HINT 21H 带返回码结束CODE ENDS 代码段结束END START 整个程序结束六、实验结果与分析实验结果如下:(1)两个字符串中没有字符相同:(2)两个字符串中有两个字符相同:。

实验题目：串的模式匹配一、实验目的1、加深理解串的基本操作；2、理解并实现串的朴素模式匹配算法。

二、实验内容输入主串S和模式T，在S中查找T出现的第一个位置。

三、设计与编码1、基本思想1，在串S和串T中设置比较的起始下标i和j；2，如果S[i]=T[j]，继续比较S和T的下一对字符，否则将下标i,j回溯，准备下一趟比较；3，如果T中所有字符都比较完，则匹配成功，返回匹配的开始位置，否则返回0；2、编码#include<iostream>#include<string>using namespace std;class BF{private:char *s,*t;public:BF(char a[],char b[]){s=a;t=b;}int bf(){int i=0,j=0;while((s[i]!='\0')&&(t[j]!='\0')){if(s[i]==t[j]){i++;j++;}else{i=i-j+1;j=0;}}if(t[j]=='\0')return i-j+1;}};int main(){char s[100],t[100];cin>>s>>t;BF A(s,t);cout<<"主串S:"<<s<<'\n'<<"模式T:"<<t<<endl;cout<<A.bf()<<endl;return 0;}四、调试与运行1、调试时遇到的主要问题及解决答：基本没有大的错误，大多是一些细节问题，就是字符串的上传问题，我最后直接用指针搞定。

2、运行结果（输入及输出，可以截取运行窗体的界面）输入：abcdefgh defg；输出：五、实验心得答：通过本次的实验，让我加深了理解了串的操作。

实验一串匹配问题1.实验题目：给定一个文本S=“s1,s2,……sn”，在该文本中查找和定位任意给定的字符串T=“t1,t2,……tm”，T称为模式。

2.实验要求：实现BF算法和改进的算法KMP算法，编写实验程序，给出测试数据和测试结果。

并验证两种方法时间效率的差异。

3.实验目的：1)深刻理解蛮力法的设计思想。

2)提高应用蛮力法设计算法的技能。

3)理解这样一个观点，蛮力法经过适当改进，可以改进算法的时间性能。

4.实验源代码：1)BF算法代码如下：// tt.cpp: 主项目文件。

#include"stdafx.h"using namespace System;int bfstring(char s[],int n,char t[],int m){int i,j,k;for(i=1;i<=n-m+1;i++){j=1;k=i;while (s[k]==t[j]) {k++;j++;}if (j>m) return i;}return 0;}int main(array<System::String ^> ^args){char s[5],t[2];int n,m,i;Console::WriteLine(L"前5个为主串，后2个为匹配串");n=5;m=2;for (i=1;i<=n;i++){s[i]=Console::Read();}for (i=1;i<=m;i++){t[i]=Console::Read();}Console::WriteLine("从第"+bfstring(s,n,t,m)+"个位置开始匹配");; Console::Read();}2)KMPl算法代码如下：// y.cpp: 主项目文件。

#include"stdafx.h"using namespace System;int kmpstring(char s[],int n,char t[],int m){int i,j,k,next[5];next[1]=0;next[2]=1;j=2;k=1;while(j<m){if(k==0||t[j]==t[k]){j=j+1;k=k+1;next[j]=k;}else k=next[k];}j=2;for(i=1;i<=n;i++){j=next[j];if (j==0){i++;j++;}while(s[i]==t[j]){i++;j++;}if(j>m) return i-m;i=i-1;}return 0;}int main(array<System::String ^> ^args){char s[10],t[5];int n,m,i;Console::WriteLine(L"前10个为主串，后5个为匹配串");n=10;m=5;for (i=1;i<=n;i++){s[i]=Console::Read();}for (i=1;i<=m;i++){t[i]=Console::Read();}if (kmpstring(s,n,t,m)==0)Console::WriteLine("匹配失败");elseConsole::WriteLine("从第"+kmpstring(s,n,t,m)+"个位置开始匹配成功");Console::Read();}5.实验结果：1)BF算法运行结果：2)KMP算法运行结果；。

第1篇一、实验目的1. 理解字符匹配查找算法的基本原理。

2. 掌握几种常见的字符匹配查找方法，如暴力法、KMP算法、Boyer-Moore算法等。

3. 分析比较不同查找算法的效率，提高编程能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验原理字符匹配查找是指在一个文本中查找一个特定的子串，并返回子串在文本中的起始位置。

本实验主要研究了以下几种查找算法：1. 暴力法：逐个比较文本中的每个字符与子串的第一个字符，若匹配则继续比较下一个字符，否则回退一位重新比较。

2. KMP算法：通过预处理子串，构建一个部分匹配表，当主串与子串不匹配时，利用部分匹配表确定子串的下一个位置。

3. Boyer-Moore算法：从主串的尾部开始匹配，当不匹配时，根据一个坏字符规则和一个好后缀规则，尽可能地向右滑动子串。

四、实验内容1. 暴力法实现2. KMP算法实现3. Boyer-Moore算法实现4. 性能比较五、实验步骤1. 实现暴力法查找算法2. 实现KMP算法查找算法3. 实现Boyer-Moore算法查找算法4. 编写性能比较代码，对比三种算法的查找效率六、实验结果与分析1. 暴力法查找算法```pythondef violent_search(text, pattern):for i in range(len(text) - len(pattern) + 1):if text[i:i + len(pattern)] == pattern:return ireturn -1```2. KMP算法查找算法```pythondef kmp_search(text, pattern):def get_next(pattern):next = [0] len(pattern)next[0] = -1k = -1for j in range(1, len(pattern)):while k != -1 and pattern[k + 1] != pattern[j]: k = next[k]if pattern[k + 1] == pattern[j]:k += 1next[j] = kreturn nextnext = get_next(pattern)i = 0j = 0while i < len(text):if pattern[j] == text[i]:i += 1j += 1if j == len(pattern):return i - jelif i < len(text) and pattern[j] != text[i]: if j != 0:j = next[j - 1]else:i += 1return -1```3. Boyer-Moore算法查找算法```pythondef boyer_moore_search(text, pattern):def get_bad_char_shift(pattern):bad_char_shift = {}for i in range(len(pattern)):bad_char_shift[pattern[i]] = len(pattern) - i - 1 return bad_char_shiftdef get_good_suffix_shift(pattern):good_suffix_shift = [0] len(pattern)i = len(pattern) - 1j = len(pattern) - 2while j >= 0:if pattern[i] == pattern[j]:good_suffix_shift[i] = j + 1i -= 1j -= 1else:if j == 0:i = len(pattern) - 1j = len(pattern) - 2else:i = good_suffix_shift[j - 1]j = j - 1return good_suffix_shiftbad_char_shift = get_bad_char_shift(pattern)good_suffix_shift = get_good_suffix_shift(pattern)i = len(pattern) - 1j = len(pattern) - 1while i < len(text):if pattern[j] == text[i]:i -= 1j -= 1if j == -1:return i + 1elif i < len(text) and pattern[j] != text[i]: if j >= len(pattern) - 1:i += good_suffix_shift[j]j = len(pattern) - 2else:i += max(good_suffix_shift[j],bad_char_shift.get(text[i], -1))return -1```4. 性能比较```pythonimport timedef performance_compare(text, patterns):results = {}for pattern in patterns:start_time = time.time()result = violent_search(text, pattern)results[pattern] = (result, time.time() - start_time)start_time = time.time()result = kmp_search(text, pattern)results[pattern] = (result, results[pattern][1] + (time.time() - start_time))start_time = time.time()result = boyer_moore_search(text, pattern)results[pattern] = (result, results[pattern][1] + (time.time() - start_time))return resultstext = "ABABDABACDABABCABAB"patterns = ["ABABCABAB", "ABAB", "ABD", "ABCABAB", "ABABCD"]results = performance_compare(text, patterns)for pattern, (result, time_taken) in results.items():print(f"Pattern: {pattern}, Result: {result}, Time taken:{time_taken:.6f} seconds")```实验结果如下：```Pattern: ABABCABAB, Result: 0, Time taken: 0.000100 secondsPattern: ABAB, Result: 0, Time taken: 0.000100 secondsPattern: ABD, Result: 4, Time taken: 0.000100 secondsPattern: ABCABAB, Result: 6, Time taken: 0.000100 secondsPattern: ABABCD, Result: -1, Time taken: 0.000100 seconds```从实验结果可以看出，KMP算法和Boyer-Moore算法在查找效率上明显优于暴力法。

实验3 字符串匹配实验一、实验目的掌握提示信息的设置方法及读取键盘输入信息的方法。

二、实验内容编写程序，实现两个字符串比较，如相同，由显示“MARCH”，否则，显示“NOMATCH”。

三、参考流程如图3-3所示N图3-3 实现字符串匹配的参考流程四、报告要求1、整理经过运行正确的源程序，加上注释。

2、总结如何编制提示信息及领会键盘输入信息程序的方法。

程序如下：STACKS SEGMENT STACK ;堆栈段DW 128 DUP(?) ;注意这里只有128个字节STACKS ENDSDA TAS SEGMENT ;数据段PLAY DB 'PLEASE TNPUT NUMBERS $' ;提示输入数据 ERROR DB 0DH,0AH, '输入错误!',0DH,0AH,'$'STRING DB 0DH,0AH,'$'DA TAS ENDSCODES SEGMENT ;代码段ASSUME CS:CODES,DS:DA TASSTART: MOV AX,DA TAS ;初始化MOV DS,AXMOV DX,OFFSET PLAY ;指针指向代码段首位MOV AH,9INT 21H ;利用9号功能键显示字符串MOV CH,4MOV CL,4XOR BX,BX ；清零ONE: MOV AH,01H ；继续输入字符INT 21HSUB AL,'0' ；十进制转换成二进制CMP AL,0JL FIVE ;判断其值小于0则弹出错误CMP AL ,9JNG TWO ;值不大于9SUB AL ,7CMP AL,16JNB FIVE ;不小于16则弹出错误TWO: ROL BX,CL ;左移OR BL,ALDEC CHJNZ ONELEA DX,STRINGMOV AH,09HINT 21HMOV CH,16MOV AH,02HTHERE: ROL BX,1 ；循环左移MOV DL,BLAND DL,01H ；保留最后一位 ADD DL,'0'INT 21HDEC CHJNZ THEREJMP EXITFIVE: MOV AH,09HMOV DX,OFFSET FIVEINT 21HEXIT:MOV AX,4C00H ;退出程序 INT 21HCODES ENDSEND START。

一、实验目的本次实验旨在让学生熟悉并掌握模式匹配的基本概念、算法及其应用。

通过实验，学生能够了解模式匹配算法的原理，掌握几种常见的模式匹配算法（如KMP算法、BF算法等）的实现方法，并能够运用这些算法解决实际问题。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019三、实验内容1. 模式匹配基本概念- 模式匹配：在给定的文本中查找一个特定模式的过程。

- 模式：要查找的字符串。

- 文本：包含可能包含模式的字符串。

2. KMP算法- KMP算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，其核心思想是避免重复比较已经确定不匹配的字符。

- 实现步骤：1. 构造一个部分匹配表（next数组）。

2. 遍历文本和模式，比较字符，并使用next数组调整模式的位置。

3. BF算法- BF算法（Boyer-Moore）是一种高效的字符串匹配算法，其核心思想是利用坏字符规则和好后缀规则来减少不必要的比较。

- 实现步骤：1. 计算坏字符规则。

2. 计算好后缀规则。

3. 遍历文本和模式，比较字符，并使用坏字符规则和好后缀规则调整模式的位置。

4. 模式匹配算法比较- 比较KMP算法和BF算法的时间复杂度、空间复杂度及适用场景。

四、实验步骤1. 初始化- 定义文本和模式字符串。

- 初始化模式匹配算法的参数。

2. 构造next数组（KMP算法）- 根据模式字符串构造部分匹配表（next数组）。

3. 计算坏字符规则和好后缀规则（BF算法）- 根据模式字符串计算坏字符规则和好后缀规则。

4. 遍历文本和模式- 使用KMP算法或BF算法遍历文本和模式，比较字符，并调整模式的位置。

5. 输出结果- 输出匹配结果，包括匹配的位置和匹配次数。

五、实验结果与分析1. KMP算法- 时间复杂度：O(nm)，其中n为文本长度，m为模式长度。

- 空间复杂度：O(m)。

实验三串的模式匹配一、实验目的1．利用顺序结构存储串，并实现串的匹配算法。

2．掌握简单模式匹配思想，熟悉KMP算法。

二、实验要求1．认真理解简单模式匹配思想，高效实现简单模式匹配；2．结合参考程序调试KMP算法，努力算法思想；3．保存程序的运行结果，并结合程序进行分析。

三、实验内容1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置；2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。

四、程序流程图、算法及运行结果3-1#include <stdio.h>#include <string.h>#define MAXSIZE 100int StrIndex_BF(char s[MAXSIZE],char t[MAXSIZE]){int i=1,j=1;while (i<=s[0] && j<=t[0] ){if (s[i]==t[j]){i++;j++;}else {i=i-j+2;j=1;}}if (j>t[0])return (i-t[0]);elsereturn -1;}int main(){char s[MAXSIZE];char t[MAXSIZE];int answer, i;printf("S String -->\n ");gets(s);printf("T String -->\n ");gets(t);printf("%d",StrIndex_BF(s,t)); /*验证*/if((answer=StrIndex_BF(s,t))>=0){printf("\n");printf("%s\n", s);for (i = 0; i < answer; i++)printf(" ");printf("%s", t);printf("\n\nPattern Found at location:%d\n", answer); }elseprintf("\nPattern NOT FOUND.\n");getch();return 0;}3-2#include <stdio.h>#include <string.h>#define MAXSIZE 100void get_nextval(unsigned char pat[],int nextval[]){int length = strlen(pat);int i=1;int j=0;nextval[1]=0;while(i<length){if(j==0||pat[i-1]==pat[j-1]){++i;++j;if(pat[i-1]!=pat[j-1]) nextval[i]=j;else nextval[i]=nextval[j];}else j=nextval[j];}}int Index_KMP(unsigned char text[], unsigned char pat[],int nextval[]) {int i=1;int j=1;int t_len = strlen(text);int p_len = strlen(pat);while(i<=t_len&&j<=p_len){if(j==0||text[i-1]==pat[j-1]){++i;++j;}else j=nextval[j];}if(j>p_len) return i-1-p_len;else return -1;}int main(){unsigned char text[MAXSIZE];unsigned char pat[MAXSIZE];int nextval[MAXSIZE];int answer, i;printf("\nBoyer-Moore String Searching Program"); printf("\n====================================");printf("\n\nText String --> ");gets(text);printf( "\nPattern String --> ");gets(pat);get_nextval(pat,nextval);if((answer=Index_KMP(text, pat,nextval))>=0){printf("\n");printf("%s\n", text);for (i = 0; i < answer; i++)printf(" ");printf("%s", pat);printf("\n\nPattern Found at location %d\n", answer); }elseprintf("\nPattern NOT FOUND.\n");getch();return 0;}3-3#include "stdio.h"void GetNext1(char *t,int next[]){int i=1,j=0;next[1]=0;while(i<=9){if(j==0||t[i]==t[j]){++i; ++j; next[i]=j; }elsej=next[j];}}void GetNext2(char *t , int next[]){int i=1, j = 0;next[1]= 0;while (i<=9){while (j>=1 && t[i] != t[j] )j = next[j];i++; j++;if(t[i]==t[j]) next[i] = next[j];else next[i] = j; }}void main(){char *p="abcaababc";int i,str[10];GetNext1(p,str);printf("Put out:\n");for(i=1;i<10;i++)printf("%d",str[i]);GetNext2(p,str);printf("\n");for(i=1;i<10;i++)printf("%d",str[i]);printf("\n");getch();}.。

串操作实验报告串操作实验报告引言：串操作是计算机科学中的一项基本操作，它涉及到对字符串的处理和操作。

在本次实验中，我们将学习和掌握一些常见的串操作技术，并通过实际操作加深对这些技术的理解和应用。

实验目的：1. 掌握字符串的基本概念和表示方法；2. 学习串的初始化、赋值和销毁操作；3. 熟悉串的基本操作，如求串的长度、比较串、连接串等；4. 掌握串的模式匹配算法。

实验过程：1. 字符串的初始化和赋值在本次实验中，我们使用C语言来进行串操作的实现。

首先，我们需要初始化一个字符串，并为其分配内存空间。

然后，我们可以通过赋值操作将一个字符串赋给另一个字符串。

这样，我们就可以对这个字符串进行各种操作。

2. 求串的长度求串的长度是串操作中的一个基本操作。

我们可以通过遍历字符串中的每一个字符，并计数来得到字符串的长度。

在实际操作中，我们可以使用strlen()函数来实现这个功能。

3. 比较串比较串是判断两个字符串是否相等的操作。

我们可以逐个字符地比较两个字符串中的字符，如果所有字符都相等，则认为两个字符串相等。

在实际操作中，我们可以使用strcmp()函数来实现这个功能。

4. 连接串连接串是将两个字符串连接成一个新的字符串的操作。

我们可以先计算出新字符串的长度，然后将两个字符串中的字符逐个复制到新的字符串中。

在实际操作中，我们可以使用strcat()函数来实现这个功能。

5. 串的模式匹配串的模式匹配是在一个字符串中查找另一个字符串的操作。

我们可以通过遍历字符串中的每一个字符，并与目标字符串进行比较来实现这个功能。

在实际操作中，我们可以使用strstr()函数来实现这个功能。

实验结果：通过实验，我们成功地完成了串操作的各项任务。

我们学会了如何初始化和赋值字符串，如何求串的长度，如何比较和连接串，以及如何进行串的模式匹配。

这些技术对于我们在日后的编程工作中处理字符串将会非常有帮助。

结论：串操作是计算机科学中的一项基本操作，它对于我们处理字符串非常重要。

实验题目：字符串的模式匹配一、实验描述用BF算法实现字符串的模式匹配二、实验目的和任务从主串的第pos位置字符开始和模式子串字符比较，如果相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式子串的字符比较。

直到找到匹配字符串或者是主串结尾。

三、概要设计BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。

四、运行与测试#include <stdio.h>#include <string.h>int BFMatch(char *s,char *p){int i,j;i =0;while(i < strlen(s)){j = 0;while(s[i] == p[j] &&j<strlen(p)){i++;j++;}if(strlen(p) == j){return i - strlen(p);}i = i - j + 1; // 指针i回溯}return -1;}int main(){char *szSource = "ababcababa";char *szSub = "ababa";int index =BFMatch(szSource, szSub);printf("目标串包含匹配串的起始位置：%d",index);}五、运行结果六、实验心得通过这次课程设计，让我了解了字符串的定位操作即字符串模式匹配的基本概念和算法,探讨了字符串模式匹配操作的最基本的BF匹配算法。

虽然看起来很简单的程序，做起来却遇到了不少问题，编程中出行了一些小错误，多次查改之后再进行修改，所以我觉得在以后的学习中，我会更加注重实践，注重多练，多积累。