C语言数据结构中串的模式匹配
C语言数据结构中串的模式匹配
串的模式匹配问题:朴素算法与KMP算法
#include#include intIndex(char*S,char*T,intpos){ //返回字串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0. //其中,T非空,1<=pos<=StrLength(s). inti=pos; intj=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])returni-T[0]; elsereturn0; } intget_next(char*T,intnext[]){ //求模式串T的next函数值并存入数组next。 inti=1;next[1]=0;intj=0; while(i T[0])returni-T[0]; elsereturn0; } voidmain() { intid,j,k,i,a; printf("输入主串、子串和匹配起始位置\n"); charA[20];charB[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){ case1: {printf("\n\n你调用了功能1:"); printf("\n朴素的模式匹配算法"); k=Index(A,B,j); printf("\n该位置为:"); printf("%d\n",k); break;} case2: {printf("\n\n你调用了功能2:"); printf("\n快速模式匹配算法"); a=Index_KMP(A,B,j); printf("\n该位置为:"); printf("%d\n",a); break;} case3: {printf("\n\n你调用了功能3:"); printf("\n退出\n"); } } }while(id!=3);
#include#include intIndex(char*S,char*T,intpos){ //返回字串T在主串S中第pos个字符之后的位置。若不存在,则函数值为0. //其中,T非空,1<=pos<=StrLength(s). inti=pos; intj=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])returni-T[0]; elsereturn0; } intget_next(char*T,intnext[]){ //求模式串T的next函数值并存入数组next。 inti=1;next[1]=0;intj=0; while(i T[0])returni-T[0]; elsereturn0; } voidmain() { intid,j,k,i,a; printf("输入主串、子串和匹配起始位置\n"); charA[20];charB[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){ case1: {printf("\n\n你调用了功能1:"); printf("\n朴素的模式匹配算法"); k=Index(A,B,j); printf("\n该位置为:"); printf("%d\n",k); break;} case2: {printf("\n\n你调用了功能2:"); printf("\n快速模式匹配算法"); a=Index_KMP(A,B,j); printf("\n该位置为:"); printf("%d\n",a); break;} case3: {printf("\n\n你调用了功能3:"); printf("\n退出\n"); } } }while(id!=3); }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!