KMP实验报告.docx
实验报告题目：编制字符串匹配的KMP算法班级：理科实验四班 姓名：木三学号：* 完成日期：2016.4.17 一、需求分析1 .字符串匹配试求子串位置的定位函数，普通的字符串匹配函数时间复杂度较大 达到了 0 (m*n),而KMP算法则可以将时间复杂度简化到0 (m+n)。2 .本演示程序中，字符串的元素为除换行、退格等字符外的其他字符，字符串长 度CMAXSIZE,字符串的输入的形式为string。储存长度,从stringl开始存 储字符，并以''0'做结束标志，字符串中字符顺序不限，且允许出现重复字符, 不能出现非法字符。输入两个字符串后，输入一个整形数pos, pos<=MAXSIZE, pos的值必须合法。输出的结果为一个整形数，表示，从第一个字符串的pos位 置开始，之后的子串能否与第二个字符串匹配，若能，输出匹配首地址的编号， 若不能，输出0。3 .程序执行的命令包括：1)构造字符串1;2)构造字符串2；3 ) kmp算法；4)得到 next ；4 .测试数据1 ) stringl='abababab'string2=, aba'pos=l output=l；2 ) stringl=" abababab?string2=, aba?pos=6 output：。；二、概要设计KMP算法是D. E. Knuth与V. R. Pratt和J. H. Morris同时发现的一种模式匹配的 高效算法，可以在0 (m+n)的时间数量级上完成串的模式匹配操作。其改进 在于：每当一趟匹配过程中出现的字符比较不等时，不需要回溯i指针，而是利 用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后， 继续进行比较。为实现上述上述程序功能，应以串的定长顺序存储表示来存放字符串，且需要串 的抽象数据类型。L串的定长顺序存储表示为：define MAXSTRLEN 255用户可在255以内定义最大串长typedef char SStringMAXSTRLEN+l ； 0 号单元存放串的长度2串的抽象数据类型定义为：ADT String数据对象：D=ai | ai £CharacterSet, i=l,2,. ,n,n>=0数据关系：Rl=<ai-l,ai> |ai-l,ai i=l,2,. . ,n)基本操作：GetString (SString &S)初始条件：存在串的指针。操作结果：生成一个由键盘键入的字符串S。strlen (SString S)初始条件：串S存在。操作结果：返回S的元素个数，称为串的长度。Index(SString S,SString T,int pos)初始条件：串S和T存在，T是非空串,l<=pos<=Strlength(S)-pos+1.操作结果：若主串S中存在和串T值相同的子串，贼返回它在主串S中第pos 个字符之后第一次出现的位置；否则函数值为0。/ADT String3 .KMP算法中，用到next函数，定义：void get_ next (SString T,int next )4 .函数的调用关系图main () ->GetString () ->strlenth () ->index_KMP->get_next()三、调试分析1.在GetStringO中开始用了 gets(S), S0没有用来记录字符串的长度，导致 在后续的程序中运算出错。2. next函数在某些情况下存在缺陷。例如模式4aaaaa在和主串'aaabaaaab' 匹配时，当i=4、产4,时不匹配，需要进行多余的三次比较，实际上，因为模 式中第1、2、3、个字符和第4个字符都相等，因此不再需要和主串中第四个字 符进行比较，而可以将模式一气向右滑动4个字符的位置直接进行；5、时 的字符比较。这就是说，若按上述定义得到nextj=k,而模式中pj二pk,则当 主串中字符si和pj不比较不等时，不需要在和pk进行比较，而直接和pnextk 进行比较,即此时的next比应该和next k相同。由此得到修正算法：void get_nextval (SString T,int nextval)四、测试结果1. S='abababab?T二'aba'pos=l ：1；2. S='abababab'T='aba'pos=6 ：0；五、附录源程序文件清单：#define MAXSTRLEN 255#include<stdio. h>#include<stdlib.h>#include<string.h>int nextMAXSTRLEN+1,nextvalMAXSTRLEN+1；typedef char SStringMAXSTRLEN+1；int Index_KMP(SString S,SString T,int pos)int i,j=l；i=pos；while(i<=S0&&j<=T0)(if (j=0|Si=Tj)i+；j+；else j=nextj；)if(j>TO)return i-T0；else return 0；)void get_next(SString T,int next)int i=l,j；next l=0；j=0;while(i<T0)(if(j=O|Ti=Tj)+i；+j；next i=j；)else j=nextj；)void get_nextval(SString T, int nextval)int i=l,j=0；nextvall=0；while(i<T0)(if(j=O|Ti=Tj)(i+;j+;if (Ti!=Tj)nextvali=j；else nextvali=nextvalj；else j=nextvalj； void GetString(SString &S)(gets(S+l)；S0=strlen (S+l)；int main ()(SString S,T；int pos；GetString(S)；GetString(T)；get_next (T,next)；scanf("%d”,&pos)；printf(n%dn,Index_KMP (S,T,pos)；return 0；
