基于BF和KMP的串模式匹配算法设计与实现(C语言).doc

数据结构 KMF算法/代码#include stdafx.h#includestring.h#includemalloc.h#define MAXSTRLEN 255int k;/定义全局变量typedef char SStringMAXSTRLEN+1;/0号元素存放串的长度。int StrAssign(SString T,char *chars) / 生成一个其值等于chars的串T int i; if(strlen(chars)MAXSTRLEN) return 0; else T0=strlen(chars); for(i=1;iT,则返回值0;若S=T,则返回值=0;若ST,则返回值0 int i; for(i=1;i=S0&i=T0;+i) if(Si!=Ti) return Si-Ti; return S0-T0;/int SubString(SString Sub,SString S,int pos,int len) / 用Sub返回串S的第pos个字符起长度为len的子串。 int i; if(posS0|lenS0-pos+1) return 0; for(i=1;i=len;i+) Subi=Spos+i-1; Sub0=len; return 1; / int Index(SString S,SString T,int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0。 /其中,T非空,1posStrLength(S)。 int i,j; if(1=pos&pos=S0) i=pos; j=1; while(i=S0&jT0) return i-T0; else return 0; else return 0; /void get_next(SString T,int next) /* 求模式串T的next函数值并存入数组next 算法 4.7 */ int i=1,j=0; next1=0; while(iT0) if(j=0|Ti=Tj) +i; +j; nexti=j; else j=nextj; k=i; / int Index_KMP(SString S,SString T,int pos,int next) /* 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。 */ /* 其中,T非空,1posStrLength(S)。算法 4.6 */ int i=pos,j=1; while(i=S0&jT0) /* 匹配成功 */ return i-T0; else return 0; int main(int argc, char* argv) int m,i,j,*q;SString T,S;char p100;printf(请输入主串); scanf(%s,p); StrAssign(S,p);/生成主串S。printf(请输入子串); scanf(%s,p); StrAssign(T,p);/生成子串T。 printf(请输入在哪位置之后); scanf(%d,&m);q=(int*)malloc(i+1)*sizeof(int); / 生成T的next数组 get_next(T,q); printf(子串的next函数为: ); for(j=1;j=k;j+) printf(%d ,*(q+j); printf(n); i=Index_KMP(S,T,m,q); if(i) printf(用KMF得主串和子串在第%d个字符处首次匹配n,i