C语言数据结构中串的模式匹配
更新时间:2020年4月25日 17:31 点击:2078
C语言数据结构中串的模式匹配
串的模式匹配问题:朴素算法与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); }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
上一篇: 用C语言模仿Python函数的实例
下一篇: C语言在头文件中定义const变量详解
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 这篇文章介绍了C#判断字符串是否数字或字母的实例,有需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了PostgreSQL判断字符串是否包含目标字符串的多种方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 本文实例讲述了php字符串按照单词进行反转的方法。分享给大家供大家参考。具体分析如下:下面的php代码可以将字符串按照单词进行反转输出,实际上是现将字符串按照空格分隔到数组,然后对数组进行反转输出。...2015-03-15
- 这篇文章主要介绍了使用list stream:任意对象List拼接字符串操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-09
- 这篇文章主要介绍了MySQL 字符串拆分操作(含分隔符的字符串截取),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-22
- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- JS中默认中文字符长度和其它字符长度计算方法是一样的,但某些情况下我们需要获取中文字符串的实际长度,代码如下: 复制代码 代码如下: function strLength(str) { var realLength = 0, len = str.length, charCode = -1;...2014-06-07
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C#实现字符串转换成字节数组的简单实现方法,仅一行代码即可搞定,非常简单实用,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了PostgreSQL 字符串处理与日期处理操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-01
- 文章介绍一个实用的函数,我们如果用php substr来截取字符在中文上处理的很有问题,今天自己写了一个比较好的中文与英文字符截取的函数,有需要的朋友可以参考下。 ...2016-11-25
- 这篇文章主要介绍了C#实现对字符串进行大小写切换的方法,涉及C#操作字符串的技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25