文档介绍：该【使用KMP算法实现一个模式匹配 】是由【秋江孤影】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【使用KMP算法实现一个模式匹配 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。课程设计
数据结构
设计题目:
KMP算法实现一个模式匹配
指导老师:徐浩学生姓名:孙文莉班级:信122班
学号:129084227
2014年6月16日
一、问题描述:使用 算法实现一个模式匹配
用编写一个程序实现模式匹配的算法。要求在一个字符串中搜索某个子串,若搜索到就返回子串的位置;若未搜索到,就返回。首先要输入个主串和模式串,先根据 函数求模式串的值,利用算法进
行匹配,再用输出函数输出结果!
二、 设计思路:
该算法分为五三个模块:
第一模块 函数(利用该函数输入主串和模式串的值);
第二模块 ()(利用该函数求各串的长度);
第三模块 函数(利用该函数求出模式串的 函数值);
第四模块 ()函数(利用该函数进行主串和模式串之间的匹配);
第五模块 函数利用该函数输出匹配结果)。
个模块之间的调用关系如下图所示:图 是对整个函数的流程图。图
是对 算法的流程图;图是求 的函数值的流程图。
,next函阙
Index_KMP
i++;j++;
next[i-1]=j;
,I'Ilj=next[j-|不能匹配
i=pos-1,j=-1m=StrLength(s);n=StrLength(t);
因水平有限,最终程序清单与这个流程图不同的地方,请谅解。大致思路是一致、、、
三、数据结构定义:
#defineMAXSIZE100;
intindex_KMP(char*s,char*t,intpos);
voidget_next(char*t,int*);
用最简单的数组进行KMP模式匹配
主串:chars[10]="abcacbabb”;
模式串:chart[4]="cac”;
intnext[4];
intpos=0;
四、系统功能介绍:
求模式串的模式值 函数
用《模式匹配的算法》当主串和模式串匹配不相等是,模式串应向右移
动一段距离,此时我们需要得到模式串的 函数值。
如何求
函数, 函数值仅取决于模式本身而和主串无关。我们可以
从分析
函数的定义出发用递推的方法求得
函数值。由定义知:
设
,即有:'
, … -
= …
口」能有两种情况:
一种情况:若
= 则表明在模式串中这就
是说
,即
+1
第二种情况:若 尹则
表明在模式串中 … ,
头”
… ”此时可把求
函数值的问题看成是一个模式匹配问题,整个模式串既是主串又是模式,而当前在匹配的过程中,已有式成立,则当尹时应将模式向右滑动,使得第 个字符和“主串”中的第个字符相比较。若 ',且'
=,则说明在主串中第 个字符之前存在一个最大长度为'的子串,使得”
… '”" ' ' …j此:
同理若'尹,则将模式继续向右滑动至使第 '个字符和
对齐,依此类推,直至 和模式中的某个字符匹配成功或者不存在任何'
' …满足,此时若尹,则有: 否则若 ,
则有:
综上所述,求 函数值过程的算法如下:
voidget_next(char*t,int*next)
{ —
int『1,j=0;
next[0]=next[1]=0;
while(i<(int)StrLength(t))
{
if(j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
elsej=next[j];
}
}
模式匹配KMP算法的实现
KMP算法的思想:主串s,模式t希望某趟在si和tj匹配失败后,指针i不回溯,模式t向右“滑动”至某个位置上,使得tk对准si继续向右进行。显然,现在问题的关键是串t“滑动”到哪个位置上?不妨设位置为k,即si和tj匹配失败后,指针i不动,模式t向右“滑动”,使tk和si对准继续向右进行比较,要满足这一假设,就要有如下关系成立:"t1t2…tk-1"="si-k+1si-k+2…si-1”()式左边是tk前面的k-1个字符,右边是si前面的k-1个字符。而本趟匹配失败是在si和tj之处,已经得到的部分匹配结果是:"t1t2…tj-1"=jsi-j+1si-j+2…si-1"()因为k<j,所以有:"tj-k+1tj-k+2…tj-1"=jsi-k+1si-k+2…si-1"()式左边是tj前面的k-1个字符,右边是si前面的k-1个字符,通过()和()得到关系:"t1t2…tk-1"="tj-k+1tj-k+2…tj-1"()结论:某趟在si和tj匹配失败后,如果模式串中有满足关系(4)的子串存在,艮"模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时,模式t就可以向右“滑动”至使tk和si对准,继续向右进行比较即可。
在求得模式的next函数之后,匹配可如下进行:假设以指针i和j分别指示主串和模式中的比较字符,令i的初值为pos,j的初值为1。若在匹配过程中si尹tj,则i和j分别增1,若si尹tj匹配失败后,则i不变,j退到next[j]位置再比较,若相等,则指针各自增1,否则j再退到下一个next值的位置,依此类推。直至下列两种情况:一种是j退到某个next值时字符比较相等,则i和j分别增1继续进行匹配;另一种是j退到值为零(即模式的第一个字符失配),则此时i和j也要分别增1,表明从主串的下一个字符起和模式重新开始匹配。
算法如下:
intIndex_KMP(char*s,char*t,intpos)
{ —
inti=pos,j=1;
while(i<=m&&j<=n)
{
if(j==0||s[i]==t[j-1])
{
i++;
j++;
}
elsej=next[j];
}
if(j>n)
returni-n+1;
else
return0;
}
五、程序清单:
#include<>
#include<>
#defineMAXSIZE100
intindex_KMP(char*s,char*t,intpos);
voidget_next(char*t,int*);
chars[10]="abcacbabb”;
chart[4]="cac”;
intnext[4];
intpos=0;
intmain()
{
printf("主串是:\n",s);
printf("模式串是:\n",t);
intn;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return0;
}intindex_KMP(char*s,char*t,intpos)
{—
inti=pos,j=1;
while(i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if(j==0||s[i]==t[j-1])
{
i++;
j++;
}
elsej=next[j];
}
if(j>(int)strlen(t))
returni-strlen(t)+1;
else
return0;
}
voidget_next(char*t,int*next)
{—
int『1,j=0;
next[0]=next[1]=0;
while(i<(int)strlen(t))
{
if(j==0冏i]==t[j])
{
i++;
j++;
next[i]=j;
}
elsej=next[j];
}
}
运行与调试分析等:
不知道什么原因,明明运行成功了,就是显示不出来,水平有限~~~~(>_<)~~