字符串匹配汇编语言程序设计
课程设计
题目字符串匹配汇编语言程序设计学院自动化学院
班级电气1003班
姓名申廷进
指导教师徐腊梅
2013 年01 月17 日
课程设计任务书
学生姓名：申廷进专业班级：电气1003班
指导教师：徐腊梅工作单位：自动化学院
题目: 字符串匹配汇编语言程序设计
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1)根据提示信息，从字符输入两个字符串，实现两个字符串的比较，如
果两个字符串的字符只要有一个相同则显示“MATCH”，否则显示“NO
MATCH”。
2)可连续输入字符进行比较，直至单击“Q”或“q”键退出程序。
时间安排：
1.9 课设题目，设计内容；
1.9—1.10 查资料，算法、方案设计。
1.10—1.13 （硬）软件设计
1.14—1.15 调试程序
1．16—1.17 写课设报告
1.18 答辩
指导教师签名：年月日
系主任（或责任教师）签名：年月日
1 设计总体方案 (2)
1.1 设计目的 (2)
1.2 设计要求及其条件 (2)
1.3 设计方案 (2)
2 程序流程图分析 (3)
2.1 转移流程图的分析 (3)
2.2 流程图总体分析 (3)
3 程序段落的说明 (5)
3.1 换行回车键的定义 (5)
3.2 提示信息和字符串的定义 (5)
3.3 DOS功能和部分指令的说明 (6)
4 程序调试说明、结果记录与分析 (7)
4.1 程序调试说明 (7)
4.2 调试结果说明 (7)
4.3 分析结果 (9)
5心得体会 (9)
参考文献 (11)
附件 (12)
微型计算机简称微机，由于其具备人脑的某些功能，所以也称其为微电脑。是由大规模集成电路组成的、体积较小的电子计算机。它是以微处理器为基础，配以内存储器及输入输出接口电路和相应的辅助电路而构成的裸机。把微型计算机集成在一个芯片上即构成单片微型计算机。学习微机课程，主要内容包括微型计算机体系结构、8086微处理器和指令系统、汇编语言、设计以及微型计算机各个组成部分，而汇编语言是其中一大板块。
汇编语言编程不仅具有计算机提供给用户的最快而又最有效的语言的优势,也可以在不很了解计算机硬件的前提下使用它。在对于程序的空间和时间要求很高的场合，使用汇编语言是必不可少，甚至对于很多需要直接控制硬件的应用场合，用保护模式下的汇编语言编程也提供给了对硬件不了解的初学者一种方法。
关键词：微机汇编语言编程
字符串匹配汇编语言程序设计
1设计总体方案
1.1 设计目的
1)进一步建立微机系统的概念，加深对系统的理解和认识，培养学生应用微型计算机解决实际问题的能力；
2)进一步学习和掌握汇编语言程序的编写和应用的方法，通过较大规模程序的编写，提高编写汇编语言程序的水平和学习程序调试方法。
3)掌握提示信息的使用方法及键盘输入信息的用法。
1.2 设计要求及其条件
课程设计要求：
3)根据提示信息，从字符输入两个字符串，实现两个字符串的比较，如
果两个字符串的字符只要有一个相同则显示“MATCH”，否则显示“NO
MATCH”。
4)可连续输入字符进行比较，直至单击“Q”或“q”键退出程序。
设计初始条件：
1)采用16位微处理器 8086 CPU以及86系列微型计算机的指令系统。
2)软件设计平台可使用EMU8086软件。
1.3设计方案
本次课设主要是比较两个字符串中有没有相同的字符，如果有就显示“MATCH”，如果没有相同则显示“NO MATCH”。开始调用DOS的9号功能显示提示信息，格式是MOV DX,字符偏移地址，MOV AH,09H，INT 21H，然后调用DOS 的8号功能从键盘输入字符，格式是MOV AH,08H，INT 21H。本程序涉及到顺序、
转移等基本程序，最后程序编写好以后从键盘输入两个字符串然后可进行多次比较，直到按Q或q退出程序，我在网上搜索到一些资料跟着资料慢慢编写程序直到程序没有错误。
2 程序流程图分析
由方案设计分析可知，此次设计比较简单，先初始化程序，然后根据提示输入两个字符串，然后进行循环比较。在循环的过程中，当按下Q或q键时退出程序；当按下其它键时，程序继续运行。
流程图设计：当初始化后，根据提示输入两个字符串，若有输入判断是否为Q或q键，如果是则退出程序，程序结束，如果否则进行两字符串比较，过程比较明了，流程图分支不多，但功能能够很好的实现，流程图如图2-1所示。2.1转移流程图的分析
本流程图有三处转移，第一处是在初始化程序后面要判断退不退出程序，提示是如果你要退出就按Q或q，不退出就按任意键继续执行程序。如图2-2所示
图2-2 退出提示
另一处转移是判断两字符串是否有相等的字符，如果有则显示“MATCH”，如果不等且字符串1还没有比较完则转移到字符串偏移地址加1程序前继续执行程序，直到字符串1比较完成。
最后一处转移是判断字符串中的字符是否比较完了，如果比较完了则显示“NO MATCH”，如果没有比较完则转移到SI指向字符串的下一个字符继续执行程序直到字符串1的字符比较完。
2.2流程图总体分析
有图2-1流程图可以看出此流程图比较简洁，可以清楚的看出整个程序的运
行状况。
图2-1 信号流图
3程序段落的说明
3.1换行回车键的定义
由于要运行出来的程序美观而且容易读懂、换行的需求所以本程序有了回车的宏定义，有了回车键的宏定义在以后程序中需要回车时就可以直接调用回车的宏定义“HUICHE”了，这样可以使程序简洁明了。回车键的宏定义程序如下所示：
HUICHE MACRO ;定义一个具有回车、换行功能的宏，为程序多次回车换行所调用。
MOV DL,0DH ;用2号功能"显示"回车。
MOV AH,02H
INT 21H
MOV DL,0AH ;用2号功能"显示"换行。
MOV AH,02H
INT 21H
ENDM
3.2提示信息和字符串的定义
本程序中用了7个提示信息都是DB类型的，他们分别是STJ0、STJ1、STJ2、STJ3、STJ4、TX1、TX2，它们的程序如下所示：
STJ0 DB 0AH,0DH,'if you want to quit please press ...q/Q...','$'
STJ1 DB '******MATCH******','$' ;
STJ2 DB '*****NO MATCH*****','$'
STJ3 DB 'press any key to continue except Q/q!','$'
STJ4 DB '******************','$'
TX1 DB 'Please input the first string:','$'
TX2 DB 'Please input the second string:','$'
本程序定义了两个字符串它们的范围都是100个字符都是DB类型的，字符串的容量大小可以自己改，但不能超出范围否则字符串会溢出。
定义字符串的程序如下所示：
STRING1 DB 100 ; 100为存第一个字符串的最大可用空间的字节数。 DB ? ;预留字节，存储将要输入的第1个字符串的实际长度。 DB 100 DUP(?);预留100个字节空间，用于存放第1个字符串。 STRING2 DB 100
DB ?
DB 100 DUP(?)
3.3DOS功能和部分指令的说明
本程序调用了两个DOS功能程序，DOS 8号功能：键盘输入字符但不显示出来；DOS 9号功能：屏幕显示字符。
1)8功能的调用（键盘输入字符但不显示字符），其格式如下所示：
格式：MOV AH,08H
INT 21H
2)9号功能调用（屏幕显示字符），其格式如下所示：
格式：MOV DX,字符串的偏移地址
MOV AH,09H
INT 21H
在使用9功能调用时要注意一下问题：
①待显示的字符串必须先放在内存一数据区（DS段）中，且以‘$’符号作为结束标志。
②应当将字符串首地址的段基址和偏移地址分别存入DS和DX寄存器中。
汇编指令SCASB的说明:
在汇编语言中SCASB是一条字符串操作指令，源自“SCAn String Byte”的缩写。该指令的具体操作是：
计算 AL - byte of [ES:EDI] , 设置相应的标志寄存器的值；
修改寄存器EDI的值：如果标志DF为0，则 inc EDI；如果DF为1，则 dec EDI。
SCASB指令常与循环指令REPZ/REPNZ合用。例如，REPNZ SCASB 语句表示当寄存器ECX>0 且标志寄存器ZF=0，则再执行一次SCASB指令。
比较寄存器AL的值不相等则重复查找的字
4程序调试说明、结果记录与分析
4.1程序调试说明
程序调试，是将编制的程序投入实际运行前，用手工或编译程序等方法进行测试，修正语法错误和逻辑错误的过程。这是保证计算机信息系统正确性的必不可少的步骤。编完计算机程序，得调试所写程序是否正确，是否能满足所要求的功能。
写好程序后运行后发现基本达到要求，但是不能按q或Q退出，而且不能连续输入输出，必须要关掉再运行才能再次输入，为解决这个问题，加了一个判断，如果输入是Q或q直接跳到结束，而且这个判断设置的位子要进行选择，调试。其次，为了解决连续输入输出，在程序加一个转移，以达到连续输入，输出，而转移到哪，这也需要去慢慢调试。我为了让程序运行出来更美观在程序中加了一些”*”这样运行出来的标识就明显了。
4.2调试结果说明
当程序编译连接成功后再运行首先出来的界面如图4-1所示：
图4-1 开始界面
当你要退出直接按Q或者q都可以退出程序，当你要继续运行程序就按任意键除了Q或者q；继续运行程序以后屏幕就会让你输入字符串1和字符串2如下图4-2所示：
图4-2 输入字符串提示
输入第一个字符串后回车它会提示你输入第二个字符串，然后再回车这时就对两字符串进行比较，如果两字符串中只要有一个字符相同则显示“MATCH”图4-3所示；如果都不相同则显示“NO MATCH”图4-4所示，此程序还可以比较许多次，直到输入Q或者q时才退出程序。
图4-3 有相同的显示
图4-4 不同时的显示
4.3 分析结果
可知运行程序后，能达到设计要求，即输入两个字符串后进行比较，如果两个字符串只要有一个字符相同则显示“MATCH”；如果完全不同则显示“NO MATCH”，按Q或q直接退出程序，输出形式也与要求完全一致，程序设计成功。
5心得体会
拿到课程设计的题目部分程序都很简单，都是平时上课所学的，可是我想把程序弄得好看一点而且我想让程序多次比较按Q或者q时推出，这让我有点不知所措，后来在网上看到一个类似的程序，便想可以套用部分程序，可是网上的都没有我想要的，所以只好自己一个一个的敲上去，但最后还是达到我想要目的，整个编程下来，让我体会最深的就是DOS功能的调用，平时可能觉得一些很难的要求通过编程并不能简单实现，但是通过 DOS功能的调用可以很轻松达到，而且通过了本次课程设计，我对输入，输出的本质概念有了更深层次的理解，知道
了微机实验时的人机交换程序是如何得到的，学习了不少的知识。
总之，就我自己而言，这次课程设计是起到的它的作用，对自己有了一个锻炼的效果，并使自己对汇编语言有了一个更加清晰的了解，加强了自己的编程能力，而且学会了搜索资料，弄懂资料，并转换为自己的知识，这次课程设计使我受益匪浅！
参考文献
[1] 彭虎等编著．微机原理与接口技术（第二版）．北京：电子工业出版社，2008
[2] 杨居义编著.微机原理与接口技术项目教程.北京：清华大学出版社，2007
[3] 荆淑霞编著.微机原理与汇编语言程序设计.北京：清华大学出版社，2004
[4] 16/32位微机原理、汇编语言及接口技术（第二版）机械工业出版社钱晓捷、陈涛等。
[5] 《汇编语言程序设计教程》(周艳萍邹伟著）清华大学出版社。
[6] 《PC机汇编语言实战精解》（李春生著）南开大学出版社。
附录
HUICHE MACRO
MOV DL,0DH ;用2号功能"显示"回车。
MOV AH,02H
INT 21H
MOV DL,0AH ;用2号功能"显示"换行。
MOV AH,02H
INT 21H
ENDM
DATA SEGMENT
STJ0 DB 0AH,0DH,'if you want to quit please press ...q/Q...','$'
STJ1 DB '******MATCH******','$'
STJ2 DB '*****NO MATCH*****','$' ;
STJ3 DB 'press any key to continue except Q/q!','$'
STJ4 DB '******************','$'
TX1 DB 'Please input the first string:','$'
TX2 DB 'Please input the second string:','$'
STRING1 DB 100
DB ?
DB 100 DUP(?) ;预留100个字节空间，用于存放第1个字符串。STRING2 DB 100
DB ?
DB 100 DUP(?)
DATA ENDS
STACK1 SEGMENT ;定义一个50字节大小的堆栈段空间。
ZHAN DB 50 DUP(?)
ZHANDING EQU LENGTH ZHAN
STACK1 ENDS
CODE SEGMENT ;代码段开始。
ASSUME CS:CODE,DS:DA TA,ES:DA TA,SS:STACK1
START: MOV AX,DATA
MOV DS,AX ;
MOV ES,AX ;
MOV AX,STACK1 ;
MOV SS,AX ;
MOV SP,ZHANDING ;栈顶指针赋初值。
L0: LEA DX,STJ0 ;输入提示
MOV AH,9
INT 21H
HUICHE
LEA DX,STJ3
MOV AH,9
INT 21H
HUICHE
MOV AH,08H
INT 21H
CMP AL,'Q'
JE EXIT
CMP AL,'q'
JE EXIT
JMP L2
EXIT: MOV AH,4CH
INT 21H
L2: MOV DX, OFFSET TX1
MOV AH,9
INT 21H
HUICHE
HUICHE
MOV DX, OFFSET STRING1
MOV AH,0AH ;用10号功能输入第1个字符串。
INT 21H
HUICHE
HUICHE
MOV DX, OFFSET TX2
MOV AH,9
INT 21H
HUICHE
HUICHE
MOV DX, OFFSET STRING2 ;输入第2个字符串。
MOV AH,0AH
INT 21H
HUICHE
HUICHE
LEA DX,STJ4
MOV AH,9
INT 21H
HUICHE
CLD ; 方向标志位清0，按增址方向操作。
MOV SI, OFFSET STRING1[2]
MOV BX,0
MOV CL, STRING1[1]
MOV CH,0 ; 将第1个字符串的实际长度赋给CX. L1: PUSH CX
MOV DI, OFFSET STRING2[2]
MOV CL, STRING2[1]
MOV CH,0
MOV AL,[SI]
REPNZ SCASB
JZ A1
INC SI ;SI加1，指向第1个字符串的下一个字符。
INC BX ;记下第1个字符串已经被搜索过的字符的个数。
POP CX
CMP CX,BX
JNZ L1
MOV DX, OFFSET STJ2 ;显示"NO MACTH"。
MOV AH,9
INT 21H
HUICHE
LEA DX,STJ4
MOV AH,9
INT 21H
HUICHE
JMP START
A1: MOV DX, OFFSET STJ1 ;显示"MACTH"。
MOV AH,9
INT 21H
HUICHE
LEA DX,STJ4
MOV AH,9
INT 21H
HUICHE
HUICHE
JMP START
MOV AH,4CH ;返回DOS系统，准备结束程序。
INT 21H
CODE ENDS
END START ;程序从此处结束。
图5-1 附录说明图
本科生课程设计成绩评定表
指导教师签字：
年月日
字符串的模式匹配算法
在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx”
正则表达式
1.验证用户名和密码：（"^[a-zA-Z]\w{5,15}$"）正确格式："[A-Z][a-z]_[0-9]"组成,并且第一个字必须为字母6~16位； 2.验证电话号码：（"^(\d{3,4}-)\d{7,8}$"）正确格式：xxx/xxxx-xxxxxxx/xxxxxxxx； 3.验证手机号码："^1[3|4|5|7|8][0-9]\\d{8}$"； 4.验证身份证号（15位或18位数字）："\d{14}[[0-9],0-9xX]"； 5.验证Email地址：("^\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*$")； 6.只能输入由数字和26个英文字母组成的字符串：("^[A-Za-z0-9]+$")； 7.整数或者小数：^[0-9]+([.][0-9]+){0,1}$ 8.只能输入数字："^[0-9]*$"。 9.只能输入n位的数字："^\d{n}$"。 10.只能输入至少n位的数字："^\d{n,}$"。 11.只能输入m~n位的数字："^\d{m,n}$"。 12.只能输入零和非零开头的数字："^(0|[1-9][0-9]*)$"。 13.只能输入有两位小数的正实数："^[0-9]+(\.[0-9]{2})?$"。 14.只能输入有1~3位小数的正实数："^[0-9]+(\.[0-9]{1,3})?$"。 15.只能输入非零的正整数："^\+?[1-9][0-9]*$"。 16.只能输入非零的负整数："^\-[1-9][0-9]*$"。 17.只能输入长度为3的字符："^.{3}$"。 18.只能输入由26个英文字母组成的字符串："^[A-Za-z]+$"。 19.只能输入由26个大写英文字母组成的字符串："^[A-Z]+$"。 20.只能输入由26个小写英文字母组成的字符串："^[a-z]+$"。 21.验证是否含有^%&',;=?$\"等字符："[%&',;=?$\\^]+"。 22.只能输入汉字："^[\u4e00-\u9fa5]{0,}$"。 23.验证URL："^http://([\w-]+\.)+[\w-]+(/[\w-./?%&=]*)?$"。 24.验证一年的12个月："^(0?[1-9]|1[0-2])$"正确格式为："01"～"09"和"10"～"12"。 25.验证一个月的31天："^((0?[1-9])|((1|2)[0-9])|30|31)$"正确格式为；"01"～"09"、"10"～"29"和“30”~“31”。 26.获取日期正则表达式：\\d{4}[年|\-|\.]\d{\1-\12}[月|\-|\.]\d{\1-\31}日? 评注：可用来匹配大多数年月日信息。 27.匹配双字节字符(包括汉字在内)：[^\x00-\xff] 评注：可以用来计算字符串的长度（一个双字节字符长度计2，ASCII字符计1） 28.匹配空白行的正则表达式：\n\s*\r 评注：可以用来删除空白行 29.匹配HTML标记的正则表达式：<(\S*?)[^>]*>.*?|<.*? /> 评注：网上流传的版本太糟糕，上面这个也仅仅能匹配部分，对于复杂的嵌套标记依旧无能为力 30.匹配首尾空白字符的正则表达式：^\s*|\s*$
正则表达式
本文分十四个类别对正则表达式的意义进行了解释，这十四各类别是：字符/字符类/预定义字符类/POSIX字符类/https://www.sodocs.net/doc/c23159756.html,ng.Character类/Unicode块和类别的类/边界匹配器/Greedy数量词/Reluctant数量词/Possessive数量词/Logical运算符/Back引用/引用/特殊构造。 1.1.字符 x 字符 x。例如a表示字符a \\ 反斜线字符。在书写时要写为\\\\。（注意：因为java在第一次解析时把\\\\解析成正则表达式\\，在第二次解析时再解析为\，所以凡是不是1.1列举到的转义字符，包括1.1的\\,而又带有\的都要写两次） \0n 带有八进制值 0的字符 n (0 <= n <= 7) \0nn 带有八进制值 0的字符 nn (0 <= n <= 7) \0mnn 带有八进制值 0的字符 mnn（0 <= m <= 3、0 <= n <= 7） \xhh 带有十六进制值 0x的字符 hh \uhhhh 带有十六进制值 0x的字符 hhhh \t 制表符 ('\u0009') \n 新行（换行）符 ('\u000A') \r 回车符 ('\u000D') \f 换页符 ('\u000C') \a 报警 (bell) 符 ('\u0007') \e 转义符 ('\u001B') \cx 对应于 x 的控制符 1.2.字符类 [abc] a、b或 c（简单类）。例如[egd]表示包含有字符e、g或d。 [^abc] 任何字符，除了 a、b或 c（否定）。例如[^egd]表示不包含字符e、g或d。 [a-zA-Z] a到 z或 A到 Z，两头的字母包括在内（范围） [a-d[m-p]] a到 d或 m到 p：[a-dm-p]（并集） [a-z&&[def]] d、e或 f（交集） [a-z&&[^bc]] a到 z，除了 b和 c：[ad-z]（减去） [a-z&&[^m-p]] a到 z，而非 m到 p：[a-lq-z]（减去） 1.3.预定义字符类(注意反斜杠要写两次，例如\d写为\\d) . 任何字符（与行结束符可能匹配也可能不匹配） \d 数字：[0-9] \D 非数字： [^0-9] \s 空白字符：[ \t\n\x0B\f\r] \S 非空白字符：[^\s] \w 单词字符：[a-zA-Z_0-9] \W 非单词字符：[^\w] 1.4.POSIX 字符类（仅 US-ASCII)(注意反斜杠要写两次，例如\p{Lower}写为\\p{Lower})
微机原理实验2程序 - 字符串匹配实验
8086汇编语言程序实验： 实验二、字符串匹配实验 题目： 1、（必做题）编程实现：从键盘分别输入两个字符串（不必等长）， 然后进行比较，若两个字符串有相同的字符，则显示“MATCH”，若字符都不相同则显示“NO MATCH”。 2、（选做题）编程实现：从键盘分别输入两个字符串，然后进行比 较，若两个字符串的长度和对应字符都完全相同，则显示“MATCH”，否则显示“NO MATCH”。 对应程序如下所示： ;第1题 ;==================================== HUICHE MACRO ;定义一个具有回车、换行功能的宏，为程序多次回车换行所调用。 MOV DL,0DH ;用2号功能“显示”回车。 MOV AH,02H INT 21H MOV DL,0AH ;用2号功能“显示”换行。 MOV AH,02H INT 21H ENDM DA TA SEGMENT MESSAGE1 DB 'MATCH','$' ;定义“MATCH”提示信息，“$”作为调用9号功能的结束符。 MESSAGE2 DB 'NO MATCH','$' ;定义“NO MATCH”提示信息。 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 100 DB ? DB 100 DUP(?) DA TA ENDS
字符串匹配算法总结
Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible
汇编语言查找匹配字符串
汇编语言实验二查找匹配字符串 一、目的 查找匹配字符串SEARCH 二、实验内容 程序接收用户键入的一个关键字以及一个句子。如果句子中不包含关键字则显示‘NO match！’；如果句子中包含关键字则显示‘MATCH’，且把该字在句子中的位置用十六进制数显示出来。 流程图
N Y Y Y 输入关键字 结束 关键字长度=0 输入句子 句子长度<关键字长度 Y 保存关键字长度到cx，cx 入栈，保存总循环次数(句子长度-关键字长度+1) 到al，将句子的首地址放进bx(作为基址寄存器)si=di=0(变址寄存器) 开始比较[bx+di]与[si]是否相等 si+1，di+1,cx-1(同时指向下一个字符) Y N bx+1(句子指向下一个字符)cx 出栈，再入栈，si,di 清零，al-1cx 是否为0 N 匹配完成，调用子程序输出 al 是否为0 不匹配，输出三、设计和编码 DATA SEGMENT mess1DB 'Enter keyword:','$'mess2DB 'Enter Sentence:','$'mess3DB 'Match at location:','$'mess4DB 'NOT MATCH.',13,10,'$'mess5DB 'H if the sentence',13,10,'$'
change DB13,10,'$' stoknin1label byte max1db10 act1db? stokn1db10dup(?) stoknin2label byte max2db50 act2db? stokn2db50dup(?) DATA ENDS STACKS SEGMENT ;此处输入堆栈段代码 STACKS ENDS CODE SEGMENT ;*************************************代码段 main proc far assume cs:code,ds:data,es:data START: push ds sub AX,AX sub BX,BX sub DI,DI sub SI,SI push AX;为返回dos并清空后面要用到的寄存器 MOV AX,DATA MOV DS,AX LEA DX,mess1 MOV ah,09 INT21h;输出Enter keyword LEA DX,stoknin1 MOV ah,0ah;用21号中段的0ah号功能获取关键字 INT21h cmp act1,0 je exit;如果为空直接退出程序 a10: ;********************************输入Sentence并判断 LEA DX,change MOV ah,09 INT21h;输出回程，换行 LEA DX,mess2 MOV ah,09 INT21h;输出Enter Sentence: LEA DX,stoknin2 MOV ah,0ah INT21h;用21号中段的0ah号功能获取句子 MOV AL,act1 CBW MOV CX,AX;保存关键字长度到cx PUSH CX;cx入栈 MOV AL,act2 cmp AL,0 je a50;保存句子长度到al，若句子为空则跳转显示not match SUB AL,act1 js a50;若句子长度小于关键字长度，则跳转显示not match INC AL CBW LEA BX,stokn2;将句子的首地址放进BX MOV DI,0 MOV SI,0 a20: ;****************************************比较，内循环 MOV AH,[BX+DI] CMP AH,stokn1[SI];遇见字符不相等就跳转到a30
MySQL中的字符串模式匹配.
MySQL中的字符串模式匹配 本文关键字：MySQL 字符串模式匹配 MySQL提供标准的SQL模式匹配，以及一种基于象Unix实用程序如vi、grep 和sed的扩展正则表达式模式匹配的格式。 标准的SQL模式匹配 SQL的模式匹配允许你使用“_”匹配任何单个字符，而“%”匹配任意数目字符(包括零个字符)。在 MySQL中，SQL的模式缺省是忽略大小写的。下面显示一些例子。注意在你使用SQL模式时，你不能使用=或!=；而使用LIKE或NOT LIKE比较操作符。 例如，在表pet中，为了找出以“b”开头的名字： +--------+--------+---------+------+------------+------------+ | name | owner | species | sex | birth | death | +--------+--------+---------+------+------------+------------+ | Buffy | Harold | dog | f | 1989-05-13 | NULL | | Bowser | Diane | dog | m | 1989-08-31 | 1995-07-29 | +--------+--------+---------+------+------------+------------+ 为了找出以“fy”结尾的名字：
+--------+--------+---------+------+------------+-------+ | name | owner | species | sex | birth | death | +--------+--------+---------+------+------------+-------+ | Fluffy | Harold | cat | f | 1993-02-04 | NULL | | Buffy | Harold | dog | f | 1989-05-13 | NULL | +--------+--------+---------+------+------------+-------+ 为了找出包含一个“w”的名字： +----------+-------+---------+------+------------+------------+ | name | owner | species | sex | birth | death | +----------+-------+---------+------+------------+------------+
KMP字符串模式匹配算法解释
个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种表示法好理解啊： KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos [23:39:35] 王尧说："^\d+$"//非负整数（正整数+ 0） "^[0-9]*[1-9][0-9]*$"//正整数 "^((-\d+)|(0+))$"//非正整数（负整数+ 0） "^-[0-9]*[1-9][0-9]*$"//负整数 "^-?\d+$"//整数 "^\d+(\.\d+)?$"//非负浮点数（正浮点数+ 0） "^(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*))$"//正浮点数 "^((-\d+(\.\d+)?)|(0+(\.0+)?))$"//非正浮点数（负浮点数+ 0） "^(-(([0-9]+\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\.[0-9]+)|([0-9]*[1-9][0-9]*)))$"//负浮点数 "^(-?\d+)(\.\d+)?$"//浮点数 "^[A-Za-z]+$"//由26个英文字母组成的字符串 "^[A-Z]+$"//由26个英文字母的大写组成的字符串 "^[a-z]+$"//由26个英文字母的小写组成的字符串 "^[A-Za-z0-9]+$"//由数字和26个英文字母组成的字符串 "^\w+$"//由数字、26个英文字母或者下划线组成的字符串 "^[\w-]+(\.[\w-]+)*@[\w-]+(\.[\w-]+)+$"//email地址 "^[a-zA-z]+://(\w+(-\w+)*)(\.(\w+(-\w+)*))*(\?\S*)?$"//url /^(d{2}|d{4})-((0([1-9]{1}))|(1[1|2]))-(([0-2]([1-9]{1}))|(3[0|1]))$/ //年-月-日 /^((0([1-9]{1}))|(1[1|2]))/(([0-2]([1-9]{1}))|(3[0|1]))/(d{2}|d{4})$/ //月/日/年 ^(\w+((-\w+)|(\.\w+))*)\+\w+((-\w+)|(\.\w+))*\@[A-Za-z0-9]+((\.|-)[A-Za-z0-9]+)*\.[A-Za-z0-9]+$ //Emil "(d+-)?(d{4}-?d{7}|d{3}-?d{8}|^d{7,8})(-d+)?" //电话号码 "^(d{1,2}|1dd|2[0-4]d|25[0-5]).(d{1,2}|1dd|2[0-4]d|25[0-5]).(d{1,2}|1dd|2[0-4]d|25[0-5]).(d{1, 2}|1dd|2[0-4]d|25[0-5])$" //IP地址 匹配中文字符的正则表达式：[\u4e00-\u9fa5] 匹配双字节字符(包括汉字在内)：[^\x00-\xff] 匹配空行的正则表达式：\n[\s| ]*\r 匹配HTML标记的正则表达式：/<(.*)>.*<\/\1>|<(.*) \/>/ 匹配首尾空格的正则表达式：(^\s*)|(\s*$) 匹配Email地址的正则表达式：^(\w+((-\w+)|(\.\w+))*)\+\w+((-\w+)|(\.\w+))*\@[A-Za-z0-9]+((\.|-)[A-Za-z0-9]+)*\.[A-Za-z0-9]+$ 匹配网址URL的正则表达式：^[a-zA-z]+://(\\w+(-\\w+)*)(\\.(\\w+(-\\w+)*))*(\\?\\S*)?$ 匹配帐号是否合法(字母开头，允许5-16字节，允许字母数字下划线)：^[a-zA-Z][a-zA-Z0-9_]{4,15}$ 匹配国内电话号码：(\d{3}-|\d{4}-)?(\d{8}|\d{7})? 匹配腾讯QQ号：^[1-9]*[1-9][0-9]*$ 漢字 Private Ps_KanjiRegex As String = "\u00A0-\u303F\u3200-\u33CF\u4E00-\uFF60\uFFA0-\uFFE5" ''入力可能漢字のコード（正規表現チェック用） 实验三字符串匹配程序 教学目标：通过教学让学生掌握显示提示信息的方法及接收键盘输入信息的方法。 重点、难点： 重点：字符串匹配的算法，用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 MACRO MOV AH,02H MOV DL,0DH INT 21H MOV AH,02H MOV DL,0AH INT 21H ENDM DATA SEGMENT MESS1 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 81 ACTLEN1 DB ? STRING1 DB 81 DUP(?) MAXLEN2 DB 81 ACTLEN2 DB ? STRING2 DB 81 DUP(?) DATA ENDS STACK SEGMENT STA DB 20 DUP(?) TOP EQU LENGTH STA STACK ENDS CODE SEGMENT ASSUME CS:CODE,DS:DA TA,SS:STACK,ES:DATA START: MOV AX,DA TA MOV DS,AX MOV AX,DA TA MOV ES,AX MOV AX,STACK MOV SS,AX MOV SP,TOP ;段寄存器及堆栈初始化 MOV AH,09H MOV DX,OFFSET MESS3 INT 21H ；显示输入提示1 MOV AH,0AH MOV DX,OFFSET MAXLEN1 INT 21H ；接收键入的字符串1 CRLF ；回车换行 MOV AH,09H MOV DX,OFFSET MESS4 INT 21H ；显示输入提示2 MOV AH,0AH MOV DX,OFFSET MAXLEN2 INT 21H ；接收键入的字符串2 CRLF CLD 太原理工大学现代科技学院 课程实验报告专业班级 学号 姓名 指导教师 一、实验目的 掌握提示信息的使用方法及键盘输入信息的用法。 二、实验内容 1、编写程序,实现两个字符串比较。如果两个字符串中有一个字符相同,显示“MATCH”,否则,显示“NO MATCH”。 2、程序框图 三、所用仪器与软件 仪器:电脑一台 软件:Masm for Windows 集成实验环境 2009、7 四、实验方法、步骤 1、编写程序代码 2、运行程序,修改错误代码 3、再次运行代码直至运行出正确结果 五、源码程序编制及分析注释 CRLF MACRO 宏定义 MOV AH,02H AH=02H MOV DL,0DH DL=0DH INT 21H 系统功能调用,输出回车字符 MOV AH,02H AH=02H MOV DL,0AH DL=0A INT 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 定义最大长度为81 ACTLEN2 DB ? STRING2 DB 81 DUP (?) 定义STRING2长度为81 DATA ENDS 数据段结束 STACK SEGMENT STACK 定义堆栈段 STA DB 50 DUP (?) 定义50个数据储存单元 TOP EQU LENGTH STA 给TOP赋值50 STACK ENDS 堆栈段结束 CODE SEGMENT 定义代码段 ASSUME CS:CODE,DS:DATA,ES:DATA,SS:STACK 定义段基址 START: MOV AX,DATA MOV DS,AX 把DATA的首地址赋给DS MOV ES,AX 把DATA的首地址赋给ES MOV AX,STACK MOV SS,AX 把STACK的首地址赋给SS MOV SP,TOP 给SP赋值50 MOV AH,09H AH=09H MOV DX,OFFSET MESS3 把MESS3的偏移地址赋给DX INT 21H 系统功能调用 MOV AH,0AH AH=0AH MOV DX,OFFSET MAXLEN1 把MAXLEN1的偏移地址赋给DX INT 21H 系统功能调用 CRLF MOV AH,09H AH=09H MOV DX,OFFSET MESS4 把MESS4的偏移地址赋给DX INT 21H 系统功能调用 MOV AH,0AH AH=0AH 数据结构面试之十四——字符串的模式匹配 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 十四、字符串的模式匹配 1. 模式匹配定义——子串的定位操作称为串的模式匹配。 2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法） 【算法思想】： 第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。 第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。 比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。 对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。 【算法实现】： //普通字符串匹配算法的实现 int Index(char* strS, char* strT, int pos) { //返回strT在strS中第pos个字符后出现的位置。 int i = pos; int j = 0; int k = 0; int lens = strlen(strS); int lent = strlen(strT); while(i < lens && j < lent) { if(strS[i+k] == strT[j]) { ++j; //模式串跳步 ++k; //主串(内)跳步 } else { i = i+1; j=0; //指针回溯，下一个首位字符 k=0; } }//end i if(j >= lent) { return i; } else { return 0; } }//end [算法时间复杂度]：设主串长度为m,模式串的长度为n。一般情况下n 要想学会正则表达式，理解元字符是一个必须攻克的难关。 不用刻意记 .：匹配任何单个字符。 例如正则表达式“b.g”能匹配如下字符串：“big”、“bug”、“bg”，但是不匹配“buug”，“b..g”可以匹配“buug”。 [ ] ：匹配括号中的任何一个字符。 例如正则表达式“b[aui]g”匹配bug、big和bag，但是不匹配beg、baug。可以在括号中使用连字符“-”来指定字符的区间来简化表示，例如正则表达式[0-9]可以匹配任何数字字符，这样正则表达式“a[0-9]c”等价于“a[0123456789]c”就可以匹配“a0c”、“a1c”、“a2c”等字符串；还可以制定多个区间，例如“[A-Za-z]”可以匹配任何大小写字母，“[A-Za-z0-9]”可以匹配任何的大小写字母或者数字。 ( ) ：将()之间括起来的表达式定义为“组”(group)，并且将匹配这个表达式的字符保存到一个临时区域,这个元字符在字符串提取的时候非常有用。把一些字符表示为一个整体。改变优先级、定义提取组两个作用。 | ：将两个匹配条件进行逻辑“或”运算。 'z|food'能匹配"z"或"food"。'(z|f)ood'则匹配"zood"或"food"。 *：匹配0至多个在它之前的子表达式，和通配符*没关系。 例如正则表达式“zo*”能匹配“z”、“zo”以及“zoo”；因此“.*”意味着能够匹配任意字符串。"z(b|c)*"→zb、zbc、zcb、zccc、zbbbccc。"z(ab)*"能匹配z、zab、zabab（用括号改变优先级）。 + ：匹配前面的子表达式一次或多次，和*对比（0到多次）。 例如正则表达式9+匹配9、99、999等。“zo+”能匹配“zo”以及“zoo”，不能匹配"z"。 ? ：匹配前面的子表达式零次或一次。 例如，"do(es)?"可以匹配"do"或"does"。一般用来匹配“可选部分”。 {n} ：匹配确定的n次。 "zo{2}"→zoo。例如，“e{2}”不能匹配“bed”中的“e”，但是能匹配“seed”中的两个“e”。 {n,} :至少匹配n次。 例如，“e{2,}”不能匹配“bed”中的“e”，但能匹配“seeeeeeeed”中的所有“e”。 {n,m}：最少匹配n次且最多匹配m次。 “e{1,3}”将匹配“seeeeeeeed”中的前三个“e” ^（shift+6）：匹配一行的开始。 例如正则表达式“^regex”能够匹配字符串“regex我会用”的开始，但是不能匹配“我会用regex”。 ^另外一种意思：非！（暂时不用理解） $ ：匹配行结束符。 例如正则表达式“浮云$”能够匹配字符串“一切都是浮云”的末尾，但是不能匹配字符串“浮云呀” 实验7、字符串查找 目的 掌握字符串模式匹配的经典算法。 问题描述 分别用简单方法和KMP方法实现index在文本串中查找指定字符串的功能。 步骤 1.定义字符串类型 2.实现简单的index操作，从文本串中查找指定字符串。 3.实现KMP方法的index操作，从文本串中查找指定字符串。 4.[选]建立一个文本文件，读入每一行来测试自己完成的练习，观察并理解程序的各 个处理。 设备和环境 PC计算机、Windows操作系统、C/C++开发环境 结论 能够理解和掌握字符串模式匹配的典型算法。 思考题 1.对KMP算法分别用手工和程序对某个模式串输出next和nextval。 朴素算法： #include #define ERROR -2 #define MAXLEN 100//字符串的最大长度 char S[MAXLEN+10],T[MAXLEN+10],st[MAXLEN+10];//串S和串T int S0,T0; //S0：串S的长度 T0：串T的长度 int pos; //pos的起始位置 void Init(char *S,int &S0)//读入字符串 { int len,i; New_Input: scanf("%s",st);//读入字符串 len=strlen(st); if (len>MAXLEN)//如果字符串的长度大于规定的字符串最大长度 { printf("This String is too long,Please Input a new one.nn"); goto New_Input;//重新读入字符串 实验题目：字符串的模式匹配 一、实验描述 用BF算法实现字符串的模式匹配 二、实验目的和任务 从主串的第pos位置字符开始和模式子串字符比较，如果相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式子串的字符比较。直到找到匹配字符串或者是主串结尾。 三、概要设计 BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配，若相等，则继续比较S的第二个字符和P的第二个字符；若不相等，则比较S的第二个字符和P的第一个字符，依次比较下去，直到得出最后的匹配结果。 四、运行与测试 #include { char *szSource = "ababcababa"; char *szSub = "ababa"; int index =BFMatch(szSource, szSub); printf("目标串包含匹配串的起始位置：%d",index); } 五、运行结果 六、实验心得 通过这次课程设计，让我了解了字符串的定位操作即字符串模式匹配的基本概念和算法,探讨了字符串模式匹配操作的最基本的BF匹配算法。虽然看起来很简单的程序，做起来却遇到了不少问题，编程中出行了一些小错误，多次查改之后再进行修改，所以我觉得在以后的学习中，我会更加注重实践，注重多练，多积累。 大学学生实验报告 （2010 —2011 学年第二学期） 课程名称：微型计算机原理与接口技术开课实验室：205 2011年 5 月 30 日年级、专业、班电信091 学号姓名成绩 实验项目名称字符匹配程序指导 教师 教 师 评语教师签名： 年月日 一、实验目的、要求 1．掌握提示信息的使用方法及键盘输入信息的用法。 二、实验原理及基本技术路线图或实验内容 1.编写程序，实现两个字符串比较。如果两个字符串中有一个字符相同，显示“MATCH”，否则，显示“NO MATCH”。 2.程序框图 段寄存器及堆栈初始化 显示“请输入字符串1” 使用INT 21H的0A号子功能， 接收键入的字符串 显示“请输入字符串2” 指针SI指向串1的首字符 SI指向的字符串和串2中所有字符作比较 Y 相等？ N SI+1，指向串1中下一字符 N 串1中的字符已取完？ Y 显示“NO MATCH”显示“MATCH” 返回DOS 三、所用仪器、材料和软件 软件名称为：MASM FOR Windows 集成实验环境2009.7 四、实验方法、步骤 根据实验的目的在该环境中编写出源代码，在进行调试、运行后，看能否得出结果。 五、源码程序编制及分析注释 程序清单及注释 CRLF MACRO ；宏定义 MOV AH,02H ；AH=02H MOV DL,0DH ；DL=0DH INT 21H ；系统功能调用来输出个回车字符 MOV AH,02H ；AH=02H MOV DL,0AH ；DL=0AH INT 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=50 STACK ENDS ；堆栈段定义结束 CODE SEGMENT ；代码段定义 ASSUME CS:CODE,DS:DATA,ES:DATA,SS:STACK ；段分配 START: MOV AX,DATA ； MOV DS,AX ；将数据段的段地址赋给DS MOV ES,AX ；将数据段的段地址赋给ES MOV AX,STACK ； 字符串匹配算法的研究及其程序实现 计算机学院计算机科学与技术专业2007级指导教师：滕云 摘要：在字符串匹配算法之中，最古老和最著名的是由D. E. Knuth, J. h. Morris, V. R. Pratt 在1997年共同提出的KMP算法。直至今日，人们对字符串匹配问题还在进行着大量的研究，以寻求更简单，或者平均时间复杂度更优的算法;学者们在不同的研究方向上，设计出了很多有效的匹配算法。在现实生活中，串匹配技术的应用十分广泛，其主要领域包括：入侵检测，病毒检测，信息检索，信息过滤，计算生物学，金融检测等等。在许多应用系统中，串匹配所占的时间比重相当大，因此，串匹配算法的速度很大程度上影响着整个系统的性能。该论文重点分析了KMP算法的实现原理和C语言实现，并在此基础上提出了改进的KMP算法，使得该算法更方便实用。 关键词：KMP算法；时间复杂度；串匹配；改进；方便使用； String matching algorithm and Implementation of the Program College of Computer Sciences, Computer Science and Technology Professional grade 2007, Instructor YunTeng Abstractor:Among the string matching algorithm,the oldest and most famous is KMP algorithm co-sponsored by D.E Knuth, J. h. Morris, VR Pratt in 1997. As of today, a lot of research to String matching are still in progress, to seek a more simply or better average time complexity of the algorithm. In different research direction, scholars have designed a lot of valid matching.In real life, the string matching technique is widely used，The main areas include: intrusion detection, virus detection, information retrieval, information filtering, computational biology, financial inspection and so on.In many applications，a large percentage of the time was placed by the string matching, so the string matching algorithms significantly affect the speed performance of the whole system.The paper analyzes the implementation of the KMP algorithm theory and through the C language to achieve it.And we puts forward a modified KMP algorithm in order to makes the algorithm more convenient and practical. Key words:KMP algorithm; Time complexity; String matching; Improved; Easy to use;正则表达式
微机原理实验三 字符串匹配程序.
微机原理__字符匹配程序实验报告
C语言字符串模式匹配
正则表达式快速记忆法
字符串模式匹配
字符串的模式匹配实验报告
微机原理字符串匹配
字符串匹配算法的研究_本科论文