模式匹配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