模式匹配KMP算法数据结构课设

三．概要设计

1.概要分析

对该KMP算法，串的抽象数据类型的定义如下：

ADT String {

数据对象：D={ai |ai￠CharacterSet ,i=1,2.......,n,n>=0} 数据关系：R1={ | ai-1,i=1,2,.....,n} 基本操作：

StrAssign(&T,chars)

初始条件：chars是字符串常量；

操作结果：生成一个其值等于chars的串t;

StrCopy(&T,S)

初始条件：串S存在；

操作结果：由串S复制得串t；

StrEmpty(S)

初始条件：串S存在；

操作结果：若串s为空串，则返回true,否则返回false；

StrCompare(S,T)

初始条件：串s和t存在；

操作结果：若S>T,则返回>0,若S

StrLength(S)

初始条件：串s存在；

操作结果：返回s的元素个数，即为串的长度；

ClearString(&S)

初始条件：串s存在； 操作结果：将s清为空串；

Concat(&T,s1,s2)

初始条件：串s1和s2存在；

操作结果：用T返回由s1和s2连接而成的新串；

SubString(&Sub,S,pos,len)

初始条件：串s存在，1<=pos<=StrLength(S);

Index(S,T,pos)

初始条件：串s和t存在，t是非空串

操作结果：若主串s中存在和串t值相同的子串，则返回它在主串s中第pos个字符之后长度为第一次出现的位置，否则函数值为0；

}ADT String

2.函数流程图

3.详细设计

求模式串的模式值GetNext()函数

用KMP模式匹配算法，当主串和模式串匹配不相等时，模式串应向右移动一段距离，此时要得到模式串的next函数值.

如何求next函数，可用递归方法求得next函数值,在当前的匹配过程中，已有Pj-k+1=P1, Pj-k+2=P2,........Pj-1=Pk-1,则当Pj!=Pk时应将模式向右滑动至第next[k]个字符和第j个字符相比较，若next[k]=k’,且Pj=Pk’，则说明在主串中第j+1个字符之前存在一个长度为k’的最长子串，和模式串中从首字符起长度为k’的子串相等，即’p1......pk’=’Pj-k+1.........Pj’。

也就是说，next[j+1]=k’+1, 即next[j+1]=next[k]+1,同理，若Pj!=Pk，则将模式继续向右滑动直至将模式中第next[k’]个字符和Pj对齐，...........以此类推，直至Pj和模式中某个字符匹配成功或不存在任何k’满足’p1......pk’=’Pj-k+1.........Pj’，则next[j+1]=1

求next函数值过程的伪码算法如下：

void GetNext(char T[MAXSTRLEN],int (&next)[64],int m) {

int i,j; i=0;

next[0]=-1;

for(j=1; j

i=next[j-1];

while(T[j]!=T[i+1]&&i>=0) i=next[i]; if(T[j]==T[i+1]) next[j]=i+1; else next[j]=-1; }

for(j=0; j<=m; j++) {

printf(\ if((j+1)%5==0) printf(\ }

cout<

模式匹配KMP实现

在求得模式匹配的next函数值后，指针i,j分别表示主串和模式串正待比较的字符，i的初值为pos，j的初值为1，若在匹配过程中Si=Pj，则i,j分别增1，否则，i不变，j退到next[j]继续比较，若相等，则i,j都增1，否则j再退到下一个next值的位置，，以此类推，有两种可能：一是j退到某个next值时字符比较相等，则指针各自增1，继续匹配；另一种是，j退到值为0，则此时将模式串再向右滑动一个位置，重新开始匹配。

IndexKMP伪代码算法如下：

int IndexKMP(char S[MAXSTRLEN],char T[MAXSTRLEN],int (&next)[64]) {

int i,j,n,m; i=j=1;

n=(int)S[0]; m=(int)T[0];

while((i

{

++i; ++j; }

else j=next[j]; if(j>=m) return i+1-m; else return 0; }

四．源程序实现代码

C++实现代码：

#include #include #include #include #include #define MAXSTRLEN 64 using namespace std;

//如果next[j]>=0,则主串的指针i不变，而且将指针j移动到next[j]的位置继续匹配

void GetNext(char T[MAXSTRLEN],int (&next)[64])// int (&next)[64]表示定义一个数组指针，next指向含有64个元素的一维数组 {

int i,j; i=1;

next[1]=j=0; while(i<(int)T[0])

if(j==0||T[i]==T[j]) {

++i; ++j;

next[i]=j; }

else j=next[j]; for(j=1; j<(int)T[0]; j++) {

printf(\ if((j)%5==0) printf(\ }

cout<

void GetNext(char T[MAXSTRLEN],int (&next)[64],int m)