您当前位置:设计在线网 >> Asp.Net >> 浏览文章

数据结构中的几个经典程序:串的模式匹配

分享到:
本文章讲述了数据结构中的几个经典程序:串的模式匹配.

串的模

式匹配问题:朴素算法与KMP算法

#include stdio.h#include string.h int Index(char*S,char*T,int pos){//返回字串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0.//其中,T非空,1=pos=StrLength(s).int i=pos;int j=1;while(i=S[0]&&j=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j T[0])return i-T[0];else return 0;}int get_next(char*T,int next){//求模式串T的next函数值并存入数组next。

int i=1;next[1]=0;int j=0;while(i T[0]){if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}else j=next[j];}return*next;}int Index_KMP(char*S,char*T,int pos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法,其中T非空,1=pos=StrLength(S).int next[100];*next=get_next(T,next);int j=1,i=pos;while(i=S[0]&&j=T[0]){if(j==0||S[i]==T[j]){++i;++j;}else j=next[j];}if(j T[0])return i-T[0];else return 0;}void main(){int id,j,k,i,a;printf("输入主串、子串和匹配起始位置\n");char A[20];char B[10];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("\n\n你调用了功能1:");printf("\n朴素的模式匹配算法");k=Index(A,B,j);printf("\n该位置为:");printf("%d\n",k);break;}case 2:{printf("\n\n你调用了功能2:");printf("\n快速模式匹配算法");a=Index_KMP(A,B,j);printf("\n该位置为:");printf("%d\n",a);break;}case 3:{printf("\n\n你调用了功能3:");printf("\n退出\n");}}}while(id!=3);#include stdio.h#include string.h int Index(char*S,char*T,int pos){//返回字串T在主串S中第pos个字符之后的位置。

若不存在,则函数值为0.//其中,T非空,1=pos=StrLength(s).int i=pos;int j=1;while(i=S[0]&&j=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j T[0])return i-T[0];else return 0;}int get_next(char*T,int next){//求模式串T的next函数值并存入数组next。int i=1;next[1]=0;int j=0;while(i T[0]){if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}else j=next[j];}return*next;}int Index_KMP(char*S,char*T,int pos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法,其中T非空,1=pos=StrLength(S).int next[100];*next=get_next(T,next);int j=1,i=pos;while(i=S[0]&&j=T[0]){if(j==0||S[i]==T[j]){++i;++j;}else j=next[j];}if(j T[0])return i-T[0];else return 0;}void main(){int id,j,k,i,a;printf("输入主串、子串和匹配起始位置\n");char A[20];char B[10];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("\n\n你调用了功能1:");printf("\n朴素的模式匹配算法");k=Index(A,B,j);printf("\n该位置为:");printf("%d\n",k);break;}case 2:{printf("\n\n你调用了功能2:");printf("\n快速模式匹配算法");a=Index_KMP(A,B,j);printf("\n该位置为:");printf("%d\n",a);break;}case 3:{printf("\n\n你调用了功能3:");printf("\n退出\n");}}}while(id!=3);}

推荐阅读:
asp.net 如何真正实现完全跨域单点登录
有关Web.config详解+asp.net优化知识
什么是ASP.NET MVC以及其优点介绍
推荐文章  
赞助商链接  
热门排行  
主题推广  
中国设计在线网 All Rights Reserved. 互联网违法和不良信息举报
信息产业部备案号:湘ICP备09001063号