KMP

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 #define ll long long
 8 #define N 1000010
 9 
10 char a[N],b[N];
11 int la,lb,nxt[N]={0},flag=0; 
12 
13 int main(){
14     scanf("%s%s",a+1,b+1);
15     la=strlen(a+1);
16     lb=strlen(b+1);
17     for(int i=2,j=0;i<=lb;i++){
18         while(j&&b[j+1]!=b[i]) j=nxt[j];
19         if(b[j+1]==b[i]) j++;
20         nxt[i]=j;
21     }
22     for(int i=1,j=0;i<=la;i++){
23         while(j&&b[j+1]!=a[i]) j=nxt[j];
24         if(b[j+1]==a[i]) j++;
25         if(j==lb){
26             printf("%d\n",i-lb+1);
27             j=nxt[j];
28             flag=1;
29         }
30     }
31     if(!flag) printf("-1\n");
32     
33     return 0;
34 }