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