资源描述：
《编译环境VS2013》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、//编译环境：VS2013//2013年10月12日，第一次编辑，实现Brute-Force算法和KMP算法//2013年10月14日，第二次编辑，主要增加了KMP算法中的next函数的修正值算法getnextval()//对于Brute-Force算法就是用循环结构控制，从目标串的第i=pos-1个字符开始与模式串的第j=0个字符比较。//若相等则i++，j++；否则目标串再从i-j+1个字符开始与模式串的第j=0个字符比较。//Brute-Force算法存在指针的回溯，算法效率较低，最坏的时间复杂度为O(
2、n*m)。//KMP算法主要是引入了next函数，对指针的回溯有了很好的解决。next函数用来求解模式串自身局部匹配的信息。//next函数确定了在模式串匹配不成功的第j个字符处模式串应往右移的量为j-next[j]个字符，再与目标串的失配点进行匹配。//next函数的修正值算法考虑到了在模式串中出现t[j]==t[k]，而目标串中的字符s[i]与t[j]比较不相等时的情况，//不再需要与t[k]进行比较，而直接与t[next[k]]进行比较即可，因为此时的next[j]应和next[k]值相同。//KMP算
3、法相比较于Brute-Force算法效率极大提高，时间复杂度为O(n+m)。#define_CRT_SECURE_NO_WARNINGS#include#include//包含exit()函数#include#defineINITSIZE100typedefstruct{char*ch;intlength;intstrsize;}string;voidinitstring(string*s);//初始化串函数voidstrassign(string*s
4、1,char*s2);//串赋值函数intBF_index(string*s,string*t,intpos);//Brute-Force函数voidgetnext(string*t,intnext[]);//由模式串t求出其next值voidgetnextval(string*t,intnextval[]);//由模式串t求出其nextval值intKMP_index(string*s,string*t,intpos);//KMP函数，使用getnext()函数intKMP_index2(string*s,
5、string*t,intpos);//KMP函数，使用next函数的修正值intmain()7/7{strings,t;charstr1[INITSIZE],str2[INITSIZE];intpos,i;initstring(&s);initstring(&t);printf("请输入要查找的目标串S：");gets(str1);//gets()用于获取一行字符串，中间可以有空格，以回车结束strassign(&s,str1);printf("请输入要查找的模式串T：");gets(str2);strass
6、ign(&t,str2);printf("请输入模式匹配的起始位序：");scanf("%d",&pos);i=BF_index(&s,&t,pos);if(i!=0)printf("1.Brute-Force算法匹配结果：t模式串T在目标串S中的位序为：%d",i);elseprintf("1.Brute-Force算法匹配结果：t模式匹配失败！");i=KMP_index(&s,&t,pos);if(i!=0)printf("2.KMP算法匹配结果：t模式串T在目标串S中
7、的位序为：%d",i);elseprintf("2.KMP算法匹配结果：t模式匹配失败！");i=KMP_index2(&s,&t,pos);if(i!=0)printf("3.KMP算法匹配结果(使用next函数的修正值)：t模式串T在目标串S中的位序为：%d",i);elseprintf("3.KMP算法匹配结果(使用next函数的修正值)：t模式匹配失败！");return0;}voidinitstring(string*s){7/7s->ch=(char*)m
8、alloc(sizeof(char)*INITSIZE);if(s->ch==NULL){puts("动态内存分配失败！");exit(-1);}s->length=0;s->strsize=INITSIZE;return;}voidstrassign(string*s1,char*s2){inti=0;while(s2[i]!=' ')//求出常量串s2的长度i++;if(i>s1->strsi
