文档介绍：河南工程学院《数据结构与算法》课程设计
成果报告
KMP算法的实现2014年12月29日
2. 5程序流程图
该算法分为五个模块：第一模块［Input。函数］（利用该函数输入主串和模式串）；第二模块［OutputS函数利用该函;
)
while (i <= Length(S) && j <= Length(T)) {
if(j ==0 || s[i] ==tU]){ //继续比拟后继字符++i; ++j;
} else j = next[j]; //模式串向右移动
}
if (j > t[0]) return i-t[0];// 匹配成功
else return 0;}//lndex_KMP
void main()(
int Loc, Next[255], pos=0,i=l,j=l;
LString *A,*B;
printf("输入执行KMP算法主串A并以ENTER键结束:\n主串:")；
A=lnput();〃从标准输入设备接收主串。
printf("输入执行KMP算法的模式串B并以ENTER键结束:\n模式串:")；
B=mput()；〃从标准输入设备接收模式串。
printf("\n");
printf("输入执行KMP算法从主串开始的位置并以ENTER键结束:\npos="); scanf(“％d”,&pos);〃从标准输入设备接收在主串执行KMP算法的开始位置。 while(pos<l)〃判断输入是否正确。
(
printf("输入错误请重新输入执行KMP算法的位置:\npos=");11
scanf("%d",&pos);
}
printf("\n\n匹配结果如下:\n");〃将结果输出到标准输出设备上。
printf(“匹配结果 3\n\n");
Get_next(B,Next);〃调用 Get_next 函数。
Loc二lndex_KMP(A,B,pos,Next);〃调用 lndex_KMP 函数并用 Loc 接收其函数值。 printf("对B执行Next函数的值:\n\t\t\t");〃将next输出到标准输出设备上。 for(i=l;Next[i] !=,\n';i++) printf("%d ",Next[i]);
if(Loc!=0){
printf("\n模式串在主串的第％d位置:\n\n，Loc);
printf("\t\t\tH);
Output(A);
printf("\t\t\t");
while(j<Loc){
printf("");
++j；
}
Output(B);
}
else printf(" \t\t\t 匹配失败\n\n");
if(Loc==0)
printf("\t\t\t 匹配失败\n'');
else printf("\t\t\t 匹配成功\rT);}//main
12
4测试
经历了将问题抽象成一个适当的数学模型，设计一个解此数学模型的算法, 编出程序，最终再做最后的测试与调整。

首先，根据测试程序说明输入主串，模式串以及开始匹配的位置。如以下图4：
图4输入图
最后，以Enter键结束就可以获得匹配的结果。其结果如以下图5：
输入执行KMP算法主串A并以ENT ER键结束:
主串：changhanxing
第入执行MMP算法的模式串B并以ENTER键结束：
模式串 :hanxing
输入执行KMP算法主串A并以ENT ER键结束:
主串：changhanxing
第入执行MMP算法的模式串B并以ENTER键结束：
模式串 :hanxing
X
输入执行KMP算法从主串开始的位置并以ENTER键结束:
rpos =1
匹配结果如下：
匹配结果3
对B执行Next函数的值：
0 111111
模式串在主串的第6位置：
changhanxing hanxing 匹配成功press anv key to continue
bJ图5匹配结果
13
4. 2测试结果分析
经历了屡次的测试与调整，我们最终调试出了 KMP算法的程序代码。对结果进行分析，其KMP算法与一般的匹配算法的不同在于：每当一趟匹配过程中出现字符比拟不等时，不需回溯i指针，而是利用已经得到的“局部匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比拟。如以下图6：
第——趟匹酉己ab^bcdefsaadadwgtlv 一
ab c此处不同
第二趟匹配ababcdefsaadadwgtlab c匹配成功
图6匹配过程
然而在反复的测试和调试的过程中，这个KMP算法程序并没有想象的那么成功，在调试的过程