kmp算法实验报告

今年以来我们在上级党组织的领导和区精神文明办的关心支持指导下坚持以邓小平理论和三个代表重要思想为指导认真落实科学发展观kmp算法实验报告篇一：模式匹配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个元素下标是1while(iif(Si=Tj)+i;+j;elsei=i-j+2;j=1;/*(1)if(jT.Length) return i-T.Length;/匹配成功else return 0;匹配的过程非常清晰，关键是当失配的时候程序是如何处理的？为什么要回溯，看下面的例子：S:aaaaabababcaaa T:ababcaaaaabababcaaaababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babc)如果不回溯就是aaaaabababcaaaaba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaaababc这是由T串本身的性质决定的，是因为T串本身有前后部分匹配的性质。如果T为abcdef这样的，大没有回溯的必要。改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：.ababd.ababc-ababc这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当Tj失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。数据结构上给了next值的定义：0如果j=1nextj=Maxk|11其它情况其实它就是描述前面表述的情况，关于next1=0是规定的，这样规定可以使程序简单一些，如果非要定为其它的值只要不和后面的值冲突也是可以的；而那个Max是什么意思，举个例子：T:aaab.aaaab.aaab-aaab-aaab-aaab像这样的T，前面自身部分匹配的部分不止两个，那应该往前跳到第几个呢？最近的一个，也就是说尽可能的向右滑移最短的长度。到这里，就实现了KMP的大部分内容，然后关键的问题是如何求next值？先看如何用它来进行匹配操作。将最前面的程序改写成：int Index_KMP(String S,String T,int pos)i=pos;j=1;/这里的串的第1个元素下标是1while(iif(j=0 | Si=Tj)+i;+j; /注意到这里的j=0,和+j的作用就 知道为什么规定next1=0的好处了else j=nextj;/i不变（不回溯）,j跳动if(jT.Length) return i-T.Length;/匹配成功else return 0;求next值，这也是整个算法成功的关键。前面说过了，next值表达的就是T串的自身部分匹配的性质，那么，我只要将T串和T串自身来一次匹配就可以求出来了，这里的匹配过程不是从头一个一个匹配，而是从T1和T2开始匹配，给出算法如下：void get_next(String T,int &next)i=1;j=0;next1=0;while(iif(j=0 | Ti=Tj)+i;+j; nexti=j;/*(2)*/else j=nextj;看这个函数非常像KMP匹配的函数！注意到(2)语句逻辑覆盖的时候是Ti=Tj以及i前面的、j前面的都匹配的情况下，于是先自增，然后记下来nexti=j，这样每当i有自增就会求得一个nexti，而j一定会小于等于i，于是对于已经求出来的next，可以继续求后面的next，而next1=0是已知，所以整个就这样递推的求出来了，方法非常巧妙。这样的改进已经是很不错了，但算法还可以改进，注意到下面的匹配情况：.aaac.aaaa.T串中的a和S串中的c失配，而a的next值指的还是a，那同样的比较还是会失配，而这样的比较是多余的，如果我事先知道，当Ti=Tj，那nexti就设为nextj，在求next值的时候就已经比较了，这样就可以去掉这样的多余的比较。于是稍加改进得到：void get_nextval(String T,int &next)i=1;j=0;next1=0;while(iif(j=0 | Ti=Tj) +i;+j;if(Ti!=Tj) nexti=j;else nexti=nextj;/消去多余的可能的比较,next再向前跳else j=nextj;三、 分析理论时间复杂性这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串S，并更新可以匹配到T的什么位置。为什么这个程序是O(n)的？ KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。四、 原程序和调试结果package kmp;public class kmp String s=aaaaaaaa;String p=aaaab;int next=new ints.length(); /主要计算next的值void calnext()int i,j=0;next1 = 0;next0=-1;for(i=2;iif(s.charAt(j)=s.charAt(i-1) nexti=nexti-1+1;j+; elseif(nextjnexti=nextj; j=nexti;/输出实际运算次数void display()int i=0,j=0,v;int count=0;while(iif(s.charAt(i)=p.charAt(j) i+;j+;else if(j=0)i+;else j=nextj;count+;System.out.println(+count); public static void main(String args) / TODO code application logic herekmp k=new kmp();k.calnext();k.display(); 五、 对结果的分析 进行了12次匹配，匹配成功。篇二：kmp算法实验报告数据结构实验报告学号：XX110000姓名：张三专业：计算机科学与技术 知识范畴：串 完成日期：XX年04月13日 实验题目：基于改进型KMP算法的字符串查找与替换实验内容及要求：从键盘输入三个字符串s、a、b,在串s中查找子串a，并将串s中的所有a替换为b，输出替换以后的串。注意：a和b的串长不要求相等；若s中无子串a,输出结果与串s相同。 实验目的：掌握字符串模式匹配的KMP算法。数据结构设计简要描述： SeqString:SeqString(Ta, intn) for (int i = 0; i算法设计简要描述： KMP算法 输入/输出设计简要描述：键盘输入s、a、b字符串编程语言说明：C+主要函数说明：voidSeqString:getnext(intnext)/获得NEXT数组 int KMPmatching( SeqStringT, MaxSize&t, int n); void replaces(SeqString&p, int upper, int lower); /替换 /KMP算法 程序测试简要报告： 1 / 5 源程序代码： / KMP.cpp : 定义控制台应用程序的入口点。/#includestdafx.h#includeiostream#includestring.husingnamespace std;templateclassSeqString ; template SeqString:SeqString() template 2 / 5 TdataMaxSize;int length; SeqString(); SeqString(T a, int n); void prints(); int getlength() return length; int KMPmatching(SeqString&t, int n); void replaces(SeqString&p, int upper, int lower); void getnext(int next); public: length = 0SeqString:SeqString(Ta, intn) templatevoidSeqString:prints() templatevoidSeqString:getnext(intnext) template voidSeqString:replaces(SeqString&p, intupper, intlower) 3 / 5 for (int i = 0; iMaxSize) cerr = length)for (int i = length - 1; iupper; i-) datai + k - length = datai; else for (int i = upper + 1; itemplateintSeqString:KMPmatching(SeqString&t, intn) int getlen(char *s) void main() cout b; SeqString ss(s, getlen(s); SeqString aa(a, getlen(a); SeqString bb(b, getlen(b); 4 / 5 int j = 0; int nextMaxSize; t.getnext(next); while (n s; cout a; while (nss.getlength()break; int upper = n - 1; int lower = n - aa.getlength(); ss.replaces(bb, upper, lower);5 / 5篇三：KMP算法_实验报告西安交通大学实验报告课程 数据结构 实验名称 基于串的模式匹配第 1 页共页 系别_自动化实 验 日 期 XX 年 11 月 15日 专业班级 自动化43班实 验 报 告 日 期 XX 年 11月 22 日 姓名李欣阳 学号 2140504066报 告 退 发 ( 订正 、 重做 ) 同 组 人 无 教 师 审 批 签 字一、实验目的熟练掌握串的运用，以及线性表、栈、队列等的基本操作；理解KMP模式匹配算法的原理，能够利用该算法解决实际问题。二、实验内容与要求1. 自由选择一个C程序文件作为程序的输入；2. 通过键盘输入待查找的模式串，求取并显示next数组；3. 判断该程序代码中是否包含该模式串，如果包含，输出左右该模式串在程序代码中文件中的位置（包括行数和该行的第几个字符）；4. 用KMP算法进行实现。三、问题分析3.1 KMP算法综述KMP算法是一个非常优秀的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，其时间复杂度为O（m+n）。该算法相对于普通匹配算法的改进在于：每当一趟匹配过程中出现字符比较不等时，不许回溯指针i，而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。3.2 next数组的计算正确求得next数组是实现KMP算法的关键，它决定了在匹配过程中出现字符不等时，模式串应该向右滑动的距离。next数组定义如下：?0，当j?1时?nextj?Max?k|1?k?j且p1.pk?1?pj?k?1.pj?1?，当此集合非空时? ?1，其他情况?求得next数组后，匹配按照如下方式进行：假设指针i和j分别指示主串和模式串中正待比较的字符，令i初值为pos，j的初值为1，若在匹配过程中对应位置字符相等，则i和j增1；如果出现不相等的情况，则j退到nextj的位置继续进行比较。3.3 一行多次匹配的实现由于原始的KMP算法在完成一次模式匹配后会推出算法，想要实现一行多个的模式匹配，需要设计结构存储每一行模式匹配中，模式串出现的位置。因此定义数组linepos20来存储模式串在每一行出现的位置。具体实现方法是：在进行模式匹配是，如果在主串中出现与模式相匹配的连续串，则把该串在主串中出现的位置记录到linpos数组中，此后i不归零而是继续进行匹配，知道主串中的每个字符都与模式串比较过。这样逐行重复上述算法就可以实现每一行的多次匹配。3.4 C程序文件的读入算法要求能对C程序代码文件进行模式匹配，在解决单行模式匹配问题后，需要解决的就是C程序文件的读入。在读入程序文件时有两种方式，一是整体读入文件后分行存储，另一个是分行读取，为了节省内存空间优化算法，本算法采用分行读取分行匹配的方式。文件的读取需要借助C语言文件打开函数fopen，在读取文件文件后，以n作为行与行之间的分隔符，借助fgets等函数实现C程序文件的分行读取。分行读取完成后借助单行匹配函数即可实现全文的模式匹配。四、相关数据结构及基本操作4.1 顺序串结构体的定义本算法需要用到串结构，顺序串适用一组连续的存储单元存储串值得字符序列，在串的定长顺序结构中，按照预定义的大小为每个定义的串变量分配一个固定长度的存储区，串的实际长度可以在这预定义长度内随意变动，超过预定义长度则会被舍去。结构体成员包括字符数组和数组长度，顺序串的结构体C语言定义如下：typedef struct seqstringchar stringMAX_LINE;int length;seqstring4.2 串的基本操作串的基本操作函数包含在标准函数库中，包括求串长Strlen、串赋值StrAssign、串连接Concat、串比较StrCompare、求字串SubString等，已经能够满足本算法需求，不需要重新定义新的操作函数。五、算法设计为了实现算法功能，并满足结果动态演示的需求，该算法的基本部分应该包括以下几个模块：（1）串的结构体定义（2）求next数组的函数getnext主要是借助next函数的定义式：?0，当j?1时?nextj?Max?k|1?k?j且p1.pk?1?pj?k?1.pj?1?，当此集合非空时?1，其他情况?设计循环借助if语句对每个j值对应的nextj进行逐一判断，如果是第一种和第三种情况，直接将0或者1存入next数组，当遇到第二种情况时，保持i,j不变，变换k的值，判断p1.pk?1?pj?k?1.pj?1是否成立，并将使“等式”成立的最大的k存入next数组。在求出所有j的next函数值后，输出数组即可。该函数C语言定义如下：void getnext(seqstring p,int next)int i,j;next0=-1;/next0放上-1i=0; /指向字符串每个字符的指针j=-1;while(iif(j=-1|p.stringi=p.stringj)/如果是第一个字符或遇到相同的字符 i+;j+;nexti=j;else j=nextj;printf(nj的值：);for(i=0;iprintf(nnext数组：);for(i=0;i;%4d,nexti+1); /输出next值（3）单行模式匹配函数KMP：函数参数是主串t，模式串p及next数组。从首位开始逐个比较模式穿与主串，当参与比较的两个位置字符相等时i ，j自增，当字符不相等时i保持不变，j变为nextj后继续比较。匹配成功时，列位置加入linpos数组，只带整个主串全部比较完毕。int KMP(seqstring t,seqstring p,int next)int i,j;i=j=0;linpos20=0;for(k=0;iwhile(jif(j=-1|t.stringi=p.stringj)i+;j+;else j=nextj;if(j=p.length)linposk=(i-p.length);j=0;if(linpos0!=0) return 1;if(linpos0=0) return -1;（4）主函数main：连接以上各函数，实现模式串的输入和C程序文件的读取，以及结果（模式串在主串中的位置）的输出。文件的读取需要借助C语言文件打开函数fopen，在读取文件文件后，以n作为行与行之间的分隔符，借助fgets等函数实现C程序文件的分行读取。分行读取完成后把每行构成的字符串转化为顺序串结构体，带入KMP函数即可计算出模式串在每行中的位置。当位置非空时，输出行数和位置坐标记录数组linepos即可。int main()seqstring bufstr,p;int next50;prin