- //-----------串的结构采用《数据结构》吴伟民版对于串定长顺序的描述
- //-----------串的定长顺序储存结构-------------------
- #define MAXSTRLEN 255 //最大串长
- typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度
- int next[20];
- //-----------串的定长顺序储存结构-------------------
- //-----------基本操作------------------
- int StrAssign(SString S,char *chars);
- //初始条件:
- //操作结果:生成一个其值等于串常量chars的串S
- int StrLength(SString S);
- //初始条件:串S存在
- //操作结果:返回S的元素个数。
- int StrAssign(SString S,char *chars)
- {
- int i=0,j=1;
- while(chars[i]!='\\0' && j<=MAXSTRLEN)
- {
- S[j]=chars[i];
- j++;
- i++;
- }
- if(chars[i]!='\\0')
- {
- return -1;
- }
- S[j]='\\0';
- //S[0]=StrLength(S);
- }
- int StrLength(SString S)
- {
- int i=1,count=0;
- while(S[i]!='\\0')
- {
- count++;
- i++;
- }
- return count;
- }
- //-----------基本操作------------------
- #include<stdio.h>
- #include<string.h>
- void get_next(SString T,int next[]);
- void get_next(SString T,int next[])
- { //求模式串T的next函数值并存入数组next。
- int i=1,j=0;
- next[1]=0;
- while(i<T[0])
- {
- if(j==0 || T[j]==T[i])
- {
- ++i;
- ++j;
- next[i]=j;
- }
- else j=next[j];
- }
- }
- int Index_KMP(SString S,SString T,int Pos)
- {
- int i=Pos,j=1;
- int sl,tl;
- sl=StrLength(S);
- tl=StrLength(T);
- while (i<=sl && j<=tl)
- {
- if(j==0 || S[i]==T[j])
- {
- ++i;
- ++j;
- }
- else
- {
- j=next[j];
- }
- }
- if(j>tl)
- {
- printf("匹配成功");
- return i-tl;
- }
- else
- printf("无法匹配模式");
- }
- //----------主函数
- void main()
- {
- SString S,T;
- char Tstr[20];
- int seat;
- char Str[]="TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT"; //匹配的文本序列
- StrAssign(S,Str);
- printf("请输入模式字符串:\\n");
- scanf("%s",Tstr);
- StrAssign(T,Tstr);
- get_next(T,next);
- seat=Index_KMP(S,T,1);
- printf("在第%d个位置匹配",seat)
- }
- //该片段来自于http://www.codesnippet.cn/detail/281020136703.html
来源: http://www.codesnippet.cn/detail/281020136703.html