- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- int *next=NULL; //存储子串的next值
- void main()
- {
- int *ChildString( char *p , int n );
- int i=0,j=0;
- char pristr[100]; //主串
- char substr[100]; //子串
- int nPristr=0; //主串长度
- int nSubstr=0; //子串长度
- printf("主串:\\n"); //通过键盘输入两字符串
- gets(pristr);
- printf("子串:\\n");
- gets(substr);
- nPristr=strlen(pristr); //求两字符串长度
- nSubstr=strlen(substr);
- next=ChildString(substr,nSubstr); //调用函数计算数组各个元素的值
- printf("\\n子串next数组的值:\\n");
- for( i=0; i<nSubstr; i++ )
- {
- printf("next[%d]= %d ",i,*(next+i));
- if( (i+1)%3 == 0 )
- printf("\\n");
- }
- for( i=0,j=0 ; i<nPristr,j<nSubstr ; )
- {
- if( pristr[i]==substr[j] )
- {
- i++;
- j++;
- }
- else
- {
- j=next[j];
- if(j==-1)
- {
- i++;
- j++;
- }
- }
- if( j==nSubstr )
- {
- printf("\\n\\n匹配位置:%d\\n",i-j+1);
- break;
- }
- else if( i==nPristr )
- {
- printf("\\n\\n匹配位置:0\\n");
- break;
- }
- }
- }
- int *ChildString( char *p , int n ) //计算子串的next数组的各个元素值
- {
- int *c=NULL;
- int i=0,j=0,k=0,flag=0;
- c=(int *)malloc( sizeof(int) * n );
- *(c+0)=-1;
- *(c+1)=0;
- for(j=2;j<n;j++)
- {
- for(i=j-1;i>0;i--)
- {
- flag=1;
- for(k=0;k<i;k++)
- {
- if( *(p+k) != *(p+j-i+k) )
- {
- flag=0;
- break;
- }
- }
- if(flag==1)
- {
- *(c+j)=i;
- break;
- }
- else
- *(c+j)=0;
- }
- }
- return c;
- }
- //该片段来自于http://www.codesnippet.cn/detail/160920135934.html
来源: http://www.codesnippet.cn/detail/160920135934.html