Cod sursa(job #906764)
#include <stdio.h>
#include <string.h>
#include <list>
using namespace std;
#define Nmax 2000007
char A[Nmax], B[Nmax];
int n, m, sol;
int pi[Nmax];
list <int> poz;
void read(){
A[0] = ' ';
B[0] = ' ';
scanf("%s", A+1);
scanf("%s", B+1);
n = strlen(A);
m = strlen(B);
fclose(stdin);
}
void kmp(){
int i, k;
pi[1] = 1;
k = 0;
for(i = 2; i < n; ++i){
while(k > 0 && A[k+1] != A[i])
k = pi[k];
if(A[k+1] == A[i]) ++k;
pi[i] = k;
}
k = 0;
for(i = 1; i < m; ++i){
while(k > 0 && A[k+1] != B[i])
k = pi[k];
if(A[k+1] == B[i]) ++k;
if(k == n - 1){
++sol;
poz.push_back(i - n + 1);
}
}
printf("%i\n", sol);
list <int>::iterator it, last;
it = poz.begin();
last = poz.end();
for(; it != last; ++it)
printf("%i ", *it);
printf("\n");
fclose(stdout);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
kmp();
return 0;
}