微机原理实验 查找匹配字符串

实验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、分析要点及调试后的正确程序。

实验课程名称微机原理实验实验项目名称字符串处理程序实验指导老师学生姓名学院理学院专业电子信息科学与技术年级2008级（一)班学号实验时间2010年12月20日总成绩ﻩﻩ①INT２１HPOP AＸMOＶDL, AＬOＲDL，30ＨMOV ＡＨ,2ＩNT ２1HMOV AH,４CHINT ２1HCODEﻩEＮDSEND ＳTARＴ编译源程序：如下，发现地29行有错误。

用EDIＴ命令找到错误地方,并进行修改,如下图所示：修改后保存程序，重新编译：重新编译后程序没有错误，用反汇编查看指令代码：如下图所示：运行程序,验证程序设计结果的正确性。

从键盘上输入字符串“ADKJｊkdjfｌjｄeoｗekdｊg”，共二十个字符，其中小写字母十六个,显示结果如下：由运行结果可知，程序运行正确，实现了设计要求。

②实验2课参考教材第五章练习１0的解法,但要编写一个在同一个字符串中删除字符,并将其余字符向前递补。

删除字符串中重复字符的源程序清单:;DELD.ASMDATA SEGMENTSTRN DB 80 DUP(?)LEN DB ?DATA ENDSCODE SEGMENTASSUME CS:CODE,DS:DATA,ES:DATA START: MOV AX,DATAMOV DS,AXMOV ES,AXLEA SI,STRN①MOV CL,0 AGAIN: MOV AH,1 ①INT 21HCMP AL,0DHJZ DONEMOV [SI],ALINC SIINC CLJMP AGAINDONE: MOV CH, 0MOV LEN,CLDEC SI②MOV BYTE PTR [SI+1],'$'源程序在2７行有错误,有提示的消息可知,此处需要用到变址或基址寄存器,用EDＩＴ命令找到错误的地方,并改正:此处是寄存器直接寻址，把cl的值送给标号为LEN存储单元，所以应去掉”[]”修改程序保存再编译以检查是否还有错误:有上图编译可知,程序修改正确,接下来连接成目标程序:生成的目标程序名为DELD.EＸE用反汇编命令查看程序代码:运行程序，检验程序设计的正确性:执行程序,输入字符串”DKJKLDKＥIOWEＪDLJAHNVＬ”，根据编写要求，显示的结果为“KＩＯＷEDJAHNVL“,既删除字符串中重复的字符。

汇编实验二查找匹配字符串YKK standardization office【 YKK5AB- YKK08- YKK2C- YKK18】实验三查找匹配字符串1.实验目的：查找匹配字符串SEARCH。

2. 实验要求：程序接收用户键入的一个关键字以及一个句子。

如果句子中不包含关键字则显示“No match!”；如果句子中包含关键字则显示“Match!”，且把该句子中的位置用十六进制数显示出来。

实验结果：要求程序的执行过程如下：Enter keyword:abcEnter Sentence: We are studying abc.Match at location:11H of the sentence.Enter Sentence: xyz, Ok?No match.Enter Sentence: ^C3. 实验报告要求:(1)分析要点及调试后的正确程序。

(2) 实验体会。

源代码：DATAREA SEGMENTSTRING1 DB "Enter keyword:$"STRING2 DB "Enter sentence:$"STRING3 DB "Match at location:$"STRING4 DB "No match!",13,10,"$"STRING5 DB "H of the sentence.$" keyword DB 50D,?,51D DUP(?) sentence DB 50D,?,51D DUP(?) DATAREA ENDSCODE SEGMENTMAIN PROC FARASSUME CS:CODE,DS:DATAREA,ES:DATAREA START:PUSH DSSUB AX,AXPUSH AXMOV AX,DATAREAMOV DS,AXMOV ES,AXLEA DX,STRING1MOV AH,09HINT 21HLEA DX,keywordMOV AH,0AHINT 21HMOV AH ,02HMOV DL,0AHINT 21HLEA DX,STRING2MOV AH,09HINT 21HLEA DX,sentenceMOV AH,0AHINT 21HMOV AH,02HMOV DL,0AHINT 21HLEA SI,keyword+2 ;关键词LEA DI,sentence+2MOV AX,0MOV AL,[sentence+1] ;句子字符个数MOV AH,[keyword+1] ;关键词字符个数CMP AL,AHJL NOSUB AL,AHMOV AH,0MOV CX,AXINC CXCOMPARE:PUSH CXMOV CX,3 ;建议采用mov ax,字符个数，使字符的个数不固定CLDREPZ CMPSBJZ MATCHMOV AX,3 ;建议采用mov ax,字符个数SUB AX,CXSUB SI,AX ;关键词回到词首MOV AX,2 ;建议采用mov ax,字符个数-1SUB AX,CXSUB DI,AXPOP CXLOOP COMPARENO: LEA DX,STRING4MOV AH,09HINT 21HJMP EXITMATCH: POP CXMOV BX,DILEA DX,STRING3MOV AH,09HINT 21HSUB BX,OFFSET sentence+2SUB BX,2 ;首地址所在字符串中的地址CALL CHANGELEA DX,STRING5MOV AH,09HINT 21HEXIT:RETMAIN ENDPCHANGE PROC NEAR PUSH AXPUSH BXPUSH CXPUSH DXMOV CH,4MOV CL,4 ROTATE: ROL BX,CL MOV AL,BLAND AL,0FHADD AL,30HCMP AL,3AHJL PRINTITADD AL,7H PRINTIT:MOV DL,ALMOV AH,2INT 21HDEC CHJNZ ROTATEPOP DXPOP CXPOP BXPOP AXRETCHANGE ENDP CODE ENDSEND START。

实验五 snort字符串匹配一、Snort规则语法：1.端口号：端口号仅对TCP和UDP协议有效，对ICMP和IP等网络层协议无效。

注意：（1）any 表示所有端口（2）:1024 表示比1024小且包含1024的所有端口（3）1024: 表示比1024大且包含1024的所有端口2.方向操作符（1）"->"：表示规则所施加的流的方向。

方向操作符左边的ip地址和端口号被认为是流来自的源主机，方向操作符右边的ip地址和端口信息是目标主机，（2）"<-"：左边的是目的地址和端口，右边的是源地址和端口。

（3）"<>"：它告诉snort把地址/端口号对既作为源，又作为目标来考虑。

这对于记录/分析双向对话很方便，例如telnet或者pop3会话。

3.规则Content允许用户设置规则，在数据包中搜索指定的内容并触发响应。

关键字的选项数据只能为文本、二进制数据或它们的混合。

二进制数据要放在管道符“|”中。

4.Sid这个关键字被用来识别snort规则的唯一性。

这个信息允许输出插件很容易的识别规则的ID号。

sid 的范围是如下分配的：<100 保留做将来使用100-1000,000 包含在snort发布包中>;1000,000 作为本地规则使用二、实验任务任务一检测网页上特定内容并报警（1）编写一个规则文件http-content.rules，在其中写入如下规则：alert tcp any any -> any any (msg: "Content值包含IPV6数据包"; content: "IPV6";sid:1000002; rev:7;)alert tcp any any -> any any (msg: "Content值包含红湖网数据包"; content: "|BAEC BAFE CDF8|"; sid:1000003; rev:7;)备注：由于“Content规则”只支持英文字符，对中文汉子，必须转换成十六进制字节码格式。

汇编语言实验二查找匹配字符串一、目的查找匹配字符串SEARCH二、实验内容程序接收用户键入的一个关键字以及一个句子。

如果句子中不包含关键字则显示‘NO match！’；如果句子中包含关键字则显示‘MATCH’，且把该字在句子中的位置用十六进制数显示出来。

流程图N YY Y输入关键字结束关键字长度=0输入句子句子长度<关键字长度Y保存关键字长度到cx ，cx 入栈，保存总循环次数(句子长度-关键字长度+1)到al ，将句子的首地址放进bx(作为基址寄存器) si=di=0(变址寄存器)开始比较[bx+di]与[si]是否相等si+1，di+1,cx-1(同时指向下一个字符)YN bx+1(句子指向下一个字符) cx 出栈，再入栈，si,di 清零，al-1 cx 是否为0N 匹配完成，调用子程序输出al 是否为0 不匹配，输出三、设计和编码DATA SEGMENTmess1 DB'Enter keyword:','$'mess2 DB'Enter Sentence:','$'mess3 DB'Match at location:','$' mess4 DB'NOT MATCH.',13,10,'$' mess5 DB'H if the sentence',13,10,'$'change DB 13,10,'$'stoknin1 label bytemax1 db 10act1 db?stokn1 db 10 dup(?)stoknin2 label bytemax2 db 50act2 db?stokn2 db 50 dup(?)DATA ENDSSTACKS SEGMENT;此处输入堆栈段代码STACKS ENDSCODE SEGMENT;*************************************代码段main proc farassume cs:code,ds:data,es:dataSTART:push dssub AX,AXsub BX,BXsub DI,DIsub SI,SIpush AX ;为返回dos并清空后面要用到的寄存器MOV AX,DATAMOV DS,AXLEA DX,mess1MOV ah,09INT 21h ;输出Enter keywordLEA DX,stoknin1MOV ah,0ah ;用21号中段的0ah号功能获取关键字INT 21hcmp act1,0je exit ;如果为空直接退出程序a10:;********************************输入Sentence并判断LEA DX,changeMOV ah,09INT 21h ;输出回程，换行LEA DX,mess2MOV ah,09INT 21h ;输出Enter Sentence:LEA DX,stoknin2MOV ah,0ahINT 21h ;用21号中段的0ah号功能获取句子MOV AL,act1CBWMOV CX,AX ;保存关键字长度到cxPUSH CX ;cx入栈MOV AL,act2cmp AL,0je a50 ;保存句子长度到al，若句子为空则跳转显示not match SUB AL,act1js a50 ;若句子长度小于关键字长度，则跳转显示not match INC ALCBWLEA BX,stokn2 ;将句子的首地址放进BXMOV DI,0MOV SI,0a20:;****************************************比较，内循环MOV AH,[BX+DI]CMP AH,stokn1[SI] ;遇见字符不相等就跳转到a30jne a30INC DIINC SIDEC CX ;没遇到一个相等的字符,cx-1,cx不为0则比较下一个字符,当cx为0是说明关键字比较完CMP CX,0je a40jmp a20a30:;*****************************************外循环，BX+1,清空si，di继续内循环比较INC BXDEC ALcmp AL,0je a50MOV DI,0MOV SI,0POP CXpush CXjmp a20a40:;*****************************************match,将bx减去句子的首地址加一得到关键字所在位置，调用二进制转十六进制子函数将位置输出SUB BX,offset stokn2INC BXLEA DX,changeMOV ah,09INT 21hLEA DX,mess3MOV ah,09INT 21hCALL btohLEA DX,mess5MOV ah,09INT 21hjmp a10;****************************************二进制转换十六进制btoh PROC NEARMOV CH,4rotate: MOV CL,4ROL BX,CLMOV AL,BLand AL,0fhadd AL,30hcmp al,3ahjl printitadd al,7hprintit:MOV dl,alMOV ah,2int 21hdec chjnz rotateretbtoh endpa50:;*****************************************显示not matchLEA DX,changeMOV ah,09INT 21hLEA DX,mess4MOV ah,09INT 21hjmp a10exit:retmain endpCODE 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)两个字符串中有两个字符相同:。

实验三字符串匹配程序教学目标：通过教学让学生掌握显示提示信息的方法及接收键盘输入信息的方法。

重点、难点：重点：字符串匹配的算法，用INT 21H 的09号子功能显示提示信息，用INT 21H的0A号子功能接收字符难点：用INT 21H的0A号子功能接收字符课时安排：2学时教学过程：讲解实验过程一实验目的：掌握显示提示信息的方法及接收键盘输入信息的方法二实验内容：编写程序，实现两个字符串的比较。

如相同，则显示“MATCH”,否则，显示”NO MATCH”.三程序框图（讲解流程图，介绍编写程序的思路）四实验原理1、讲解DB、DUP、EQU等伪指令的功能以及使用格式2、讲解INT 21H 的09H子功能的功能、工作情况以及使用格式3、讲解INT 21H的0AH子功能的功能、工作情况以及使用格式4、讲解串扫描指令SCASB的功能以及使用格式5、入栈、出栈指令PUSH 、POP的使用情况五实验参考程序CRLF MACROMOV AH,02HMOV DL,0DHINT 21HMOV AH,02HMOV DL,0AHINT 21HENDMDATA SEGMENTMESS1 DB 'MA TCH',0DH,0AH,'$'MESS2 DB 'NO MA TCH',0DH,0AH,'$'MESS3 DB 'INPUT STRING1:',0DH,0AH,'$'MESS4 DB 'INPUT STRING2:',0DH,0AH,'$'MAXLEN1 DB 81ACTLEN1 DB ?STRING1 DB 81 DUP(?)MAXLEN2 DB 81ACTLEN2 DB ?STRING2 DB 81 DUP(?)DATA ENDSSTACK SEGMENTSTA DB 20 DUP(?)TOP EQU LENGTH STASTACK ENDSCODE SEGMENTASSUME CS:CODE,DS:DA TA,SS:STACK,ES:DATASTART: MOV AX,DA TAMOV DS,AXMOV AX,DA TAMOV ES,AXMOV AX,STACKMOV SS,AXMOV SP,TOP ;段寄存器及堆栈初始化MOV AH,09HMOV DX,OFFSET MESS3INT 21H ；显示输入提示1MOV AH,0AHMOV DX,OFFSET MAXLEN1INT 21H ；接收键入的字符串1CRLF ；回车换行MOV AH,09HMOV DX,OFFSET MESS4INT 21H ；显示输入提示2MOV AH,0AHMOV DX,OFFSET MAXLEN2INT 21H ；接收键入的字符串2CRLFCLDMOV SI,OFFSET STRING1MOV CL,[SI-1]MOV CH,00H ；字符串1的实际字符数送CXKKK: MOV DI,OFFSET STRING2PUSH CXMOV CL,[DI-1]MOV CH,00H ；字符串2的实际字符数送CXMOV AL,[SI]MOV DX,DIREPNZ SCASB ；将串1中的一个字符和串2中的所有字符作比较JZ GGG ；比较相等转GGGINC SI ；从串1中取下一个字符POP CXLOOP KKKMOV AH,09HMOV DX,OFFSET MESS2INT 21H ；显示‘NO MA TCH'JMP PPPGGG: MOV AH,09HMOV DX,OFFSET MESS1INT 21H ;显示'MATCH'PPP: MOV AX,4C00HINT 21H ；返回DOSCODE ENDSEND START六实验步骤1、按实验要求编写程序2、汇编连接程序生成可执行文件3、执行程序观察结果七、拓展练习编写程序，实现两个字符串的比较。

字符串匹配算法的原理和实现随着互联网应用的广泛普及，各种搜索引擎、数据挖掘等技术越来越受到人们的关注。

在很多应用中，我们需要对文本进行匹配，即在一段文本中查找某个字符串是否出现过，或者查找多个字符串在文本中的位置。

这就需要用到字符串匹配算法，本文将介绍字符串匹配算法的原理和实现。

一、暴力匹配算法暴力匹配算法是最朴素的字符串匹配算法，也称为朴素算法或者蛮力算法。

它的原理非常简单，就是从文本的第一个字符开始依次比较，如果匹配失败，则将文本的指针后移一位，开始下一次比较。

具体实现可以用以下代码表示：```int search(string pattern, string text) {int n = text.length();int m = pattern.length();for(int i = 0; i < n - m + 1; i++) {int j;for(j = 0; j < m; j++) {if(pattern[j] != text[i+j]) {break;}}if(j == m) {return i;}}return -1;}```该算法的时间复杂度为O(nm)，其中n和m分别是文本和模式串的长度。

当模式串非常短时，该算法的效率还可以接受，但是当模式串很长时，算法效率就会变得很低，甚至比较文本中的每个字符都慢。

因此，我们需要更加快速和高效的算法来实现字符串匹配。

二、KMP算法KMP算法全称为Knuth-Morris-Pratt算法，它是一种比暴力匹配算法更加高效的字符串匹配算法，可以在O(n+m)的时间复杂度内完成字符串匹配。

KMP算法的基本思想是利用匹配失败后的信息来避免无谓的比较，具体过程如下：1.计算模式串的前缀函数（Prefix Function）。

前缀函数的定义是：对于模式串P的每个位置i（0 <= i < m），对应的前缀函数（Pi）表示模式串的第0个位置到第i个位置的最长的，既是最前面的，也是最后面的，与整个模式串P的某个前缀相等的后缀的长度。

第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算法在查找效率上明显优于暴力法。

实验四字符匹配程序1要求：用串操作指令设计程序。

实现在指定存储区（长度：100H）中寻找匹配字符，遇空格字符（20H）结束，显示查找结果。

2目的：掌握串操作指令的用法。

3说明：48086指令系统中用于字符串检索的指令为SCASB/SCASW，用AL中的字节或AX中的字与位于ES段由DI寄存器所指的内存单元的字节或字相比较，实现在DI所指的字符串中，寻找第一个与AL（或AX）的内容相同（或不同）的字节（或字）。

10对于所有串操作指令，都要注意方向标志的设置，指令CLD使方向标志DF清’0’，SI和DI自动增量修改，指令STD使DF置’1’，SI和DI作自动减量修改。

实验源程序DATA SEGMENTMESS1 DB'when press enter ,find the space key in6000:0-100!',0DH,0AH,'$'MESS3 DB'find the space!',0DH,0AH,'$'MESS4 DB'no space!',0DH,0AH,'$'DATA ENDSSTACK SEGMENTSTA DW 32 DUP(?)TOP DW?STACK ENDSCODE SEGMENTASSUME CS:CODE,DS:DATA,ES:DATA,SS:STACK START: MOV AX,DATAMOV DS,AX ;初始化MOV ES,AXMOV AH,09HMOV DX,OFFSET MESS1INT 21H ;显示信息1MOV AH,08HINT 21HMOV AX,6000HMOV ES,AXMOV DI,0 ;偏移量送DICLD ;清方向标志MOV CX,0100H ;长度为100H字节MOV AL,20H ;空格符20HREPNZ SCASBJNZ AA ;全都不为20H则转AAMOV AH,09HMOV DX,OFFSET MESS3INT 21H ;显示"找到"信息JMP BBBAA: MOV AH,09HMOV DX,OFFSET MESS4INT 21H ;显示"没找到"信息BBB: MOV AX,4C00HINT 21H ;结束CODE ENDSEND START运行结果。

实验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。

- 让每一个人同等地提高自我8086 汇编语言程序实验：实验二、字符串般配实验题目：1、（必做题）编程实现：从键盘分别输入两个字符串（不用等长），而后进行比较，若两个字符串有同样的字符，则显示“MATCH ”，若字符都不同样则显示“NO MATCH ”。

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

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

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

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

MOV AH,02HINT21HENDMDATA SEGMENTMESSAGE1DB'MATCH','$';定义“ MATCH ”提示信息，“ $”作为调用 9 号功能的结束符。

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

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

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

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

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

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

STRING2DB100DB?DB100DUP(?)DATA ENDS- 让每一个人同等地提高自我STACK SEGMENT;定义一个 50 字节大小的货仓段空间。

课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目: 查找字符串中的指定字符初始条件：1 做一个操作界面，提示操作：输入一串字符串、输入所查找的字符或字符串等；2 显示出查找到的数目；3 用不同颜色或闪烁标示出所找到的字符或字符串；要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）设计任务及要求分析（2）方案比较及认证说明（3）系统原理阐述（4）硬件设计课题需要说明：硬件原理，电路图，采用器件的功能说明（5）软件设计课题需要说明：软件思想，流程图，源程序及程序注释（6）调试记录及结果分析（7）总结（8）参考资料（9）附录：芯片资料或程序清单，软件演示屏幕拷贝图或硬件实物图时间安排：1月10日~1月12日：收集资料，方案选择1月13日~1月17日：整体流程，程序细节1月18日~1月20日:调试程序，报告撰写1月20：交设计报告，程序演示，答辩指导教师签名：年月日系主任（或责任教师）签名：年月日本课程设计是用汇编语言设计一个在字符串中查找指定字符并输出所查找到相同字符的个数，并将相同字符变色。

在这次课程设计中多次运用了循环程序来完成字符的输入，比较，并调用子程序来实现计数和变色功能。

运行程序时，把编写的源程序保存在clock.Asm中，在masm for windows集成环境下进行调试，首先点运行选项的调试，如果编译成功，就选择运行选项中的exe档。

这样就产生了一个可运行的程序，然后点击运行，就会看到与题目相符合的操作界面。

最后调试程序，运行程序，系统会提示错误的位置，和类型。

通过改变程序的前后联系，调试完毕后。

再进行编译连接，运行，使系统能正确连接运行为止。

最后直到系统没有一处错误为止。

关键字：字符，编译，循环，中断1设计任务及需求分析 (3)1.1题目分析 (3)1.2主要设计思路 (3)2方案设计 (4)3软件编程设计 (5)3.1输入字符串程序 (5)3.2输入要查找的字符并输出相同字符的个数 (5)3.3循环比较并将相同的字符变换颜色 (6)4系统调用的流程图 (8)5调试过程 (9)6实验结果显示 (9)心得体会 (11)参考资料 (12)附录 (13)查找字符串中的指定字符1设计任务及需求分析1.1题目分析1 做一个操作界面，提示操作：输入一串字符串、输入所查找的字符或字符串等。

大学学生实验报告（2010 —2011 学年第二学期）课程名称：微型计算机原理与接口技术开课实验室：205 2011年 5 月 30 日一、实验目的、要求1．掌握提示信息的使用方法及键盘输入信息的用法。

二、实验原理及基本技术路线图或实验内容1.编写程序，实现两个字符串比较。

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

2.程序框图三、所用仪器、材料和软件软件名称为：MASM FOR Windows 集成实验环境2009.7四、实验方法、步骤根据实验的目的在该环境中编写出源代码，在进行调试、运行后，看能否得出结果。

五、源码程序编制及分析注释程序清单及注释CRLF MACRO ；宏定义MOV AH,02H ；AH=02HMOV DL,0DH ；DL=0DHINT 21H ；系统功能调用来输出个回车字符MOV AH,02H ；AH=02HMOV DL,0AH ；DL=0AHINT 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 ；字符串1的缓冲区最大字符数ACTLEN1 DB ? ；字符串1的实际输入字符的个数STRING1 DB 81 DUP (?) ；用来存储字符串1的81个单元MAXLEN2 DB 81 ；字符串2的缓冲区最大字符数ACTLEN2 DB ? ；用来存放字符串2的实际字符个数STRING2 DB 81 DUP (?) ；用来存储字符串2的81个单元DATA 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,DATA ；MOV DS,AX ；将数据段的段地址赋给DSMOV ES,AX ；将数据段的段地址赋给ESMOV AX,STACK ；MOV SS,AX ；将堆栈段的段地址赋给SSMOV SP,TOP ；SP=50MOV AH,09H ；AH=09HMOV DX,OFFSET MESS3 ；INT 21H ；输出'INPUT STRING1:MOV AH,0AHMOV DX,OFFSET MAXLEN1INT 21H ；（DS:DX）=最大字符数，（DS:DX+1）=实际的字符数CRLFMOV AH,09HMOV DX,OFFSET MESS4INT 21H ；输出INPUT STRING2:MOV AH,0AHMOV DX,OFFSET MAXLEN2INT 21H ；（DS:DX）=最大字符数，（DS:DX+1）=实际的字符数CRLF ；宏调用CLD ；DF=0，则串操作有低地址向高地址方向进行MOV SI,OFFSET STRING1 ；将字符串1的偏移地址赋给SIMOV CL,[SI-1] ；将字符串1的字符实际个数赋给CLMOV CH,00H ；CH=00HKKK: MOV DI,OFFSET STRING2 ；将字符串2的偏移地址赋给DI PUSH CX ；将CX中的值即为字符串1的字符个数压入堆栈MOV CL,[DI-1] ；将字符串2的字符个数赋给CLMOV CH,00H ；CH=00HMOV AL,[SI] ；取出字符串1的第一个字符给ALMOV DX,DI ；将字符串2的第一个字符赋给DXREPNZ SCASB ；CX!=0（没有查完）和ZF=0（不相等）时重复JZ GGG ；ZF=1，表示已经搜到了相等的字符，则转出INC SI ；SI=SI+1POP CX ；弹出原先字符串1中剩下未被进行比较的字符个数LOOP KKK ；CX-1!=0则继续返回到子过程KKKMOV AH,09HMOV DX,OFFSET MESS2INT 21H ；否则CX=0时的系统功能调用将显示NO MATCHJMP PPP ；将跳转到PPPGGG: MOV AH,09HMOV DX,OFFSET MESS1INT 21H ；系统功能调用将显示MATCHPPP: MOV AX,4C00HINT 21H ；系统功能调用显示控制台的操作界面CODE ENDS ；代码段结束END START ；伪指令结束六、实验结果、分析和结论和体会1、实验结果如图所示2、实验分析：注意相关指令的运用与子啊存储空间中分段的运用3、体会：对一些指令进一步熟悉，对指令的执行过程有很好的了解（注：文档可能无法思考全面，请浏览后下载，供参考。

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字节大小的堆栈段空间。