KMP模式匹配算法.doc

KMP 模式匹配算法 1、需求分析输入:模式串,主串输出:一串值和匹配结果功能要求:模式串的 next 值表与匹配结果 2、设计概要 main () getnext () myStrstr () dest () sub str () 3、详细设计#include<> #include<> #include<> #include<> #include<> void getNext(const char * t,int * Next)//Next 数组{ int k=-1; int j=0; int size=strlen(t); Next[0]=1; while(j<size) { if(k==-1||t[j]==t[k]) { k++; j++; Next[j]=k; } else k=Next[k]; } for(j=0;j<size;j++) { printf("Next 表: %d",Next[j]); printf("\n"); }} int myStrstr(const char * Dest,const char *subStr) { int destSize=strlen(Dest); int subSize=strlen(subStr); int i,j; int* Next=(int *)(malloc(sizeof(int)*subSize)); i=j=0; assert((Dest!=NULL)&&(subStr!=NULL)); getNext(subStr,Next); while(i<destSize&&j<subSize) { if(j==-1||Dest[i]==subStr[j]) { i++; j++; } else j=Next[j]; } if(j==subSize)return i-j; return -1; } int main() { char *temp,*sub,* Dest; int ch; unsigned int templen,length=20*sizeof(char); unsigned int mlength=20*sizeof(char); sub=(char*)malloc(length); Dest=(char*)malloc(length); if(sub==NULL||Dest==NULL) { printf(" 输入非法! \n"); exit(0); } temp=sub; printf(" 输入模式串:\n"); while((ch=getchar())!=10) { if((temp-sub)/sizeof(char)==length) { templen=length; sub=realloc(sub,length+=20*sizeof(char)); if(sub==NULL) { printf(" 输入非法! \n"); exit(0); } temp=sub+templen*sizeof(char); } *temp++=ch; } *temp='\0'; temp=Dest; printf(" 输入主串:\n"); while((ch=getchar())!=10) { if((temp-Dest)/sizeof(char)==mlength) { templen=mlength; Dest=realloc(Dest,mlength+=20*sizeof(char));// 越界 if(Dest==NULL) { printf(" 输入非法! \n"); exit(0); } temp=Dest+templen*sizeof(char); } *temp++=ch; } *temp='\0'; printf(" 匹配起始位置为:%d\n",myStrstr(Dest,sub)); free(Dest); free(sub); return 0; getchar(); } 四、调试过程在调试过程中经常会有报错的情况, 检查显示错误时发现大都是些丢掉分号或括号等由于粗心马虎等造成的小错误,因为这个程序比较简单,因此调试过程还算顺利。五、用户使用说明(1 )首先输入模式串(2 )输入主串(3 )敲回车即输出 next 值六、运行结果 Kruskal 算法一、需求分析输入:无向图(顶点序列,边序列) 输出:一串字符和数值功能要求:输出最小生成树的各组成边及最小生成树的权值二、概要设计 main () CreatGraph () sort () MiniSpanTree () Find () 三、详细设计#include<> #include<stdli