- #include<stdio.h>
- #include<string.h>
- #define MaxSize 300001
- void GetNextval(char t[],int len2,int nextval[])
- {
- int j=0,k=-1;
- nextval[0]=-1;
- while (j<len2)
- {
- if (k==-1 || t[j]==t[k])
- {
- j++;
- k++;
- if (t[j]!=t[k])
- nextval[j]=k;
- else
- nextval[j]=nextval[k];
- }
- else k=nextval[k];
- }
- }
- int kmp(char s[],int len1,char t[],int len2)
- {
- int nextval[MaxSize],i=0,j=0;
- GetNextval(t,len2,nextval);
- while (i<len1 && j<len2)
- {
- if (j==-1 || s[i]==t[j])
- {
- i++;
- j++;
- }
- else j=nextval[j];
- }
- if (j>=len2)
- return(i-len2);
- else
- return -1;
- }
- int main()
- {
- char s[MaxSize],t[MaxSize];
- int len1,len2,k;
- scanf("%s%s",s,t);
- len1=strlen(s);len2=strlen(t);
- k=kmp(s,len1,t,len2)+1;
- if(k==0)
- printf("No\\n");
- else
- printf("%d\\n",k);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/2011201411020.html
来源: http://www.codesnippet.cn/detail/2011201411020.html