KMP算法C语言代码实现

《KMP算法C语言代码实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*在VisualStudio2008环境下调试*/#include#include#include/*改进型与非改进型区别就在于算出next[i]的值后再向前取出next[i]-1为下标的t[next[i]-1]的字符*并将其与当前不匹配的字符是否相同相同则next[i]=next[next[i]-1]*还有就是若是当前不匹配的值与字串的每一个字符相同则next[i]=0*//*（）next[1]=0意义：任何串的第一个字符的模式值规定为。（）next[j]=k意义：

2、模式串T中下标为j的字符，如果j的前面k－个字符与开头的k－个字符相等，即:T[1]T[2]……T[k-1]==T[j-k+1]T[j-k+2]…T[j-1]（）next[j]=1其他情况。*//*设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],（）、next[n]=0表示S[m]和T[1]间接比较过了，不相等，下一次比较S[m+1]和T[1]（）、next[n]=1表示比较过程中产生了不相等，下一次比较S[m]和T[1]。（）、next[n]=k表示S[m]的前k个字符与T中

3、的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]相等吗？（）、其他值，不可能。*/voidGetStrNext(chart[],intnext[])//获取next数组的值非改进型{intlen=0;inti=0,j=0,k=0,l=0,m=0,n=0;charch='';len=strlen(t);while(i

4、处k=0;while(j<=l){ch=t[j];if(ch==t[k]){m=j;n=k;while(m<=l){ch=t[m];if(ch==t[n]){n++;m++;}elsebreak;}if(m>l)next[i]=i-j+1;elsenext[i]=1;}elseif(m<=l)next[i]=1;j++;}}i++;}j=strlen(t);/*for(i=0;i

5、rt[],intnext[])//获取next数组的值改进型{intlen=0;inti=0,j=0,k=0,l=0,m=0,n=0;charch='';len=strlen(t);while(i

6、f(ch==t[n]){n++;m++;}elsebreak;}ch=t[i];if(m>l){next[i]=i-j;if(ch==t[next[i]])if(ch!=t[0])next[i]=next[next[i]];elsenext[i]=0;elseNULL;}elseif(ch!=t[0])next[i]=1;elsenext[i]=0;}elseif(m<=l&&t[i]!=t[0])next[i]=1;elsenext[i]=0;j++;}}i++;}j=strlen(t);/*for(i=0;i

7、)printf("%d",next[i]);printf("");_getch();*/}voidFindTStr(chars[],chart[],intnext[])//根据next数组的值进行查找{intlens=0,lent=0,i=0,j=0,pos=0,flag=0;lens=strlen(s);lent=strlen(t);pos=i;while(i

8、

9、j==1)break;}else{j

10、++;i++;}}if(j==lent){flag=1;printf("pos=%d",pos);//打印找到的位置//_getch();}j=0;i++;pos=i;}if(lent>lens-pos-1&&!flag)printf("NotFind!");}intmain(){