串的模式匹配问题：朴素算法与KMP算法.doc

串的模式匹配问题：朴素算法与KMP算法仰之弥高，钻之弥坚。由俭入奢易，由奢入俭难。删繁就简三秋树，领异标新二月花。南朝四百八十寺，多少楼台烟雨中。皮之不存，毛将焉附。#include#includeint Index(char *S,char *T,int pos)/返回字串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0./其中，T非空，1=pos=StrLength(s).int i=pos;int j=1;while(i=S0&jT0) return i-T0;else return 0;int get_next(char *T,int next)/求模式串T的next函数值并存入数组 i=1;next1=0;int j=0;while(iT0) if (j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;return *next;int Index_KMP(char *S,char *T,int pos)/利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法，其中T非空，1=pos=StrLength(S).int next100;*next=get_next(T,next);int j=1,i=pos;while(i=S0&jT0) return i-T0;else return 0;void main()int id,j,k,i,a;printf(输入主串、子串和匹配起始位置n);char A20;char B10;printf(请输入主字串内容n); gets(A+1); *A=strlen(A+1);printf(请输入子字串内容n); gets(B+1); *B=strlen(B+1);printf(请输匹配起始位置n); scanf(%d,&j);/printf(%d ,k); do printf(n请输入您需要的任务的序号); printf(n1:朴素的模式匹配算法); printf(n2:快速模式匹配算法); printf(n3:退出n); scanf(%d,&id); switch(id) case 1: printf(nn你调用了功能1:); printf(n朴素的模式匹配算法); k=Index(A,B,j); printf(n该位置为：); printf(%dn,k); break; case 2: printf(nn你调用了功能2:); printf(n 快速模式匹配算法); a=Index_KMP(A,B,j); printf(n该位置为：); printf(%dn,a); break; case 3: printf(nn你调用了功能3:); printf(n退出n); while(id!=3);#include#includeint Index(char *S,char *T,int pos)/返回字串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0./其中，T非空，1=pos=StrLength(s).int i=pos;int j=1;while(i=S0&jT0) return i-T0;else return 0;int get_next(char *T,int next)/求模式串T的next函数值并存入数组 i=1;next1=0;int j=0;while(iT0) if (j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;return *next;int Index_KMP(char *S,char *T,int pos)/利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法，其中T非空，1=pos=StrLength(S).int next100;*next=get_next(T,next);int j=1,i=pos;while(i=S0&jT0) return i-T0;else return 0;void main()int id,j,k,i,a;printf(输入主串、子串和匹配起始位置n);char A20;char B10;printf(请输入主字串内容n); gets(A+1); *A=strlen(A+1);printf(请输入子字串内容n); gets(B+1); *B=strlen(B+1);printf(请输匹配起始位置n); scanf(%d,&j);/printf(%d ,k); do printf(n请输入您需要的任务的序号); printf(n1:朴素的模式匹配算法); printf(n2:快速模式匹配算法); printf(n3:退出n); scanf(%d,&id); switch(id) case 1: printf(nn你调用了功能1:); printf(n朴素的模式匹配算法); k=Index(A,B,j); printf(n该位置为：); printf(%dn,k); break; case 2: printf(nn你调用了功能2:); printf(n 快速模式匹配算法); a=Index_KMP(A,B,j); printf(n该位置为：); printf(%dn,a); break; case 3: