三．概要设计
1.概要分析
对该KMP算法，串的抽象数据类型的定义如下：
ADT String {
数据对象：D={ai |ai￠CharacterSet ,i=1,2.......,n,n>=0} 数据关系：R1={
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 //如果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)