- #include<stdio.h>
- unsigned char S[300001];
- unsigned char T[300001];
- int w[300001];
- void next(int w[],int a){
- int i=1,j=0;
- w[1]=0;
- do{
- if(j==0||T[i]==T[j])
- {++i;++j;w[i]=j;
- }
- else
- j=w[j];
- }while(i<a);
- }
- void indexkmp(int w[],int a,int b){
- int i=1,j=1;
- do{
- if(j==0||S[i]==T[j]){
- ++i;++j;
- }
- else j=w[j];
- }while(i<=a&&j<=b);
- if(j>b)
- printf("%d\\n",i-b);
- else printf("No\\n");
- }
- int main()
- {
- int a,b,i=1,j=1;
- scanf("%s%s",&S[1],&T[1]);
- for(a=1;S[a]!='\\0';a++);
- for(b=1;T[b]!='\\0';b++);
- next(w,b-1);
- indexkmp(w,a-1,b-1);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1211201410948.html
来源: http://www.codesnippet.cn/detail/1211201410948.html