字符串模式匹配
实验7、字符串查找
目的
掌握字符串模式匹配的经典算法。
问题描述
分别用简单方法和KMP方法实现index在文本串中查找指定字符串的功能。
步骤
1.定义字符串类型
2.实现简单的index操作，从文本串中查找指定字符串。
3.实现KMP方法的index操作，从文本串中查找指定字符串。
4.[选]建立一个文本文件，读入每一行来测试自己完成的练习，观察并理解程序的各
个处理。
设备和环境
PC计算机、Windows操作系统、C/C++开发环境
结论
能够理解和掌握字符串模式匹配的典型算法。
思考题
1.对KMP算法分别用手工和程序对某个模式串输出next和nextval。
朴素算法：
#include
#include
#define NOTFOUND -1
#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;//重新读入字符串
}
for (i=1;i<=len;i++) S[i]=st[i-1];
S[len+1]='';
S0=len;
}
int Index(char *S,char *T,int pos)
{
if (pos<1 || pos>S0) return ERROR; // 输入数据不合法
int i=pos,j=1;
while (i<=S0 && j<=T0)
{
if (S[i]==T[j]) {i++; j++;}
else {i=i-j+2; j=1;}//不匹配时，对应S移到下一位进行匹配
}
if (j>T0) return i-T0; //返回S中找到的位置
else return NOTFOUND;
}
int main()
{
int ret;//函数返回值
Init(S,S0);
Init(T,T0);
scanf("%d",&pos);
ret=Index(S,T,pos); //在S串中从pos这个位置起，找到第一个与T匹配的子串的起始位置
if (ret==NOTFOUND) printf("Not Found.n");
else if(ret==ERROR) printf("The Input Data is Error.n");
else printf("In S,from %dth is equal to T.n",ret);
return 0;
}
KMP：
#include
#include
#define NOTFOUND -1
#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的起始位置
int next[MAXLEN+10];
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; //重新读入字符串
}
for (i=1;i<=len;i++) S[i]=st[i-1];
S[len+1]='';
S0=len;
}
void Get_next(char *S,int *next)
{
int i=1,j=0;
next[1]=0;
while (i if (j==0 || T[i]==T[j]) {i++; j++; next[i]=next[j];} else j=next[j]; } int Index_KMP(char *S,char *T,int pos) { int i=pos,j=1; while (i<=S0 && j<=T0) if (j==0 || S[i]==T[j]) {i++; j++;} else j=next[j]; if (j>T0) return i-T0; else return NOTFOUND; } int main() { int ret;//函数返回值 Init(S,S0); Init(T,T0); scanf("%d",&pos); Get_next(T,next); ret=Index_KMP(S,T,pos); //在S串中从pos这个位置起，找到第一个与T匹配的子串的起始位置 if (ret==NOTFOUND) printf("Not Found.n"); else if (ret==ERROR) printf("The Input Data is Error.n"); else printf("In S,from %dth is equal to T.n",ret); return 0; } 扩张KMP： #include #include #define NOTFOUND -1 #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的起始位置 int nextval[MAXLEN+10]; 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; //重新读入字符串 } for (i=1;i<=len;i++) S[i]=st[i-1]; S[len+1]=''; S0=len; } void Get_nextval(char *S,int *nextval) { int i=1,j=0; nextval[1]=0; while (i if (j==0 || T[i]==T[j]) { i++; j++; if (T[i]!=T[j]) nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } int Index_KMP(char *S,char *T,int pos) { int i=pos,j=1; while (i<=S0 && j<=T0) if (j==0 || S[i]==T[j]) {i++; j++;} else j=nextval[j]; if (j>T0) return i-T0; else return NOTFOUND; } int main() { int ret;//函数返回值 Init(S,S0); Init(T,T0); scanf("%d",&pos); Get_nextval(T,nextval); ret=Index_KMP(S,T,pos); //在S串中从pos这个位置起，找到第一个与T匹配的子串的起始位置 if (ret==NOTFOUND) printf("Not Found.n"); else if (ret==ERROR) printf("The Input Data is Error.n"); else printf("In S,from %dth is equal to T.n",ret); return 0; } 在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从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” 模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(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; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。 竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一：串的模式匹配算法 串的匹配算法——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]; else return0; } } bF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m). 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 实验三串的模式匹配 一、实验目的 1．利用顺序结构存储串，并实现串的匹配算法。 2．掌握简单模式匹配思想，熟悉KMP算法。 二、实验要求 1．认真理解简单模式匹配思想，高效实现简单模式匹配； 2．结合参考程序调试KMP算法，努力算法思想； 3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置； 2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。 参考程序: #include "stdio.h" void GetNext1(char *t,int next[])/*求模式t的next值并寸入next数组中*/ { int i=1,j=0; next[1]=0; while(i<=9)//t[0] { if(j==0||t[i]==t[j]) {++i; ++j; next[i]=j; } else j=next[j]; } } void GetNext2(char *t , int next[])/* 求模式t 的next值并放入数组next中 */ { int i=1, j = 0; next[1]= 0; /* 初始化 */ while (i<=9) /* 计算next[i+1] t[0]*/ { 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("\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\n"); } 汇编语言实验二查找匹配字符串 一、目的 查找匹配字符串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提供标准的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算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值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 //算法功能：串的朴素模式匹配是最简单的一种模式匹配算法，又称为 Brute Force 算法，简称为BF算法 #include int main() { SString S, T; int m; char strs1[MAXL]; //建立主串S char strs2[MAXL]; //建立模式串T printf("请输入主串和子串:\n"); printf("主串S: "); scanf("%s", strs1); printf("子串T: "); scanf("%s", strs2); StrAssign(S, strs1); StrAssign(T, strs2); m = Index(S, T, 1); if(m) printf("主串 S = {%s}\n子串 T = {%s}\n在第 %d 个位置开始匹配！\n", strs1, strs2, m); else printf("主串 S = {%s}\n子串 T = {%s}\n匹配不成功！\n", strs1, strs2); return 0; } 实验三字符串匹配程序 教学目标：通过教学让学生掌握显示提示信息的方法及接收键盘输入信息的方法。 重点、难点： 重点：字符串匹配的算法，用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 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(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:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 数据结构面试之十四——字符串的模式匹配 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 十四、字符串的模式匹配 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 太原理工大学现代科技学院 课程实验报告专业班级 学号 姓名 指导教师 一、实验目的 掌握提示信息的使用方法及键盘输入信息的用法。 二、实验内容 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 串的匹配算法——Brute Force (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非空。 int index(String S, String T ,int pos) { int i=pos; //用于主串S中当前位置下标，若pos不为1则从pos位置开始匹配int j =1; //j用于子串T中当前位置下标值 while(i<=S[0]&&j<=T[0]) //若i小于S长度且j小于T的长度时循环 { if(S[i]==T[j]) //两个字母相等则继续 { ++i； ++j； } else //指针后退重新开始匹配 { i=i-j+2; //i退回到上次匹配首位的下一位 j=1； } if(j>T[0]) return i-T[0]; else return 0; } } BF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m 次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m 从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是O(n+m). 实验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;//重新读入字符串 一、实验内容和目的 1、深刻理解并掌握蛮力算法的设计思想； 2、提高应用蛮力算法设计算法的技能； 3、理解这样一个观点:用蛮力法设计的算法，一般来说，经过适度的努 力后，都可以对算法的第一个版本进行一定程度的改良，改进其时 间性能。 二、实验原理及基本技术路线图（方框原理图） 串匹配问题——给定两个串S=“s1s2…s n” 和T=“t1t2…t m”，在主 串S中查找子串T的过程称为串匹配，也称模式匹配。 串匹配问题属于易解问题。 串匹配问题的特征： （1）算法的一次执行时间不容忽视：问题规模n 很大，常常需要在 大量信息中进行匹配； （2）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。 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右移的计算方法却发生了较大的变化。 设计思想：设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。 字符串匹配算法的研究及其程序实现 计算机学院计算机科学与技术专业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;字符串的模式匹配算法
模式匹配的KMP算法详解
串的模式匹配算法实验报告
微机原理实验2程序 - 字符串匹配实验
字符串匹配算法总结
实验三____串的模式匹配
汇编语言查找匹配字符串
MySQL中的字符串模式匹配.
KMP字符串模式匹配算法解释
串的朴素模式匹配算法(BF算法)
微机原理实验三 字符串匹配程序.
模式匹配KMP算法实验步骤
C语言字符串模式匹配
微机原理__字符匹配程序实验报告
串的模式匹配算法
字符串模式匹配
串匹配问题：BF算法、KMP算法、BM算法
字符串匹配算法的研究_本科论文
相关文档
- 微机原理实验2程序---字符串匹配实验
- 微机原理实验2程序字符串匹配实验
- 微机原理实验2程序 - 字符串匹配实验
- 微机原理字符串匹配
- 微机原理实验五 字符串匹配程序
- 字符串匹配汇编语言程序设计
- 字符串精确匹配及比对
- 字符串模式匹配
- 字符串的模式匹配实验报告
- 查找匹配字符串程序设计
- 字符串的模式匹配算法
- C程序设计(字符串查找与匹配)习题与答案 (2)
- 微机原理__字符匹配程序实验报告
- 汇编语言-实验四 字符串的匹配与替换程序设计
- 微机原理实验 查找匹配字符串
- 字符串匹配算法的研究_本科论文
- 汇编实验二查找匹配字符串
- 微机原理字符串匹配
- 微机原理实验2程序---字符串匹配实验
- 微机原理__字符匹配程序实验报告