Cod sursa(job #974068)
#include <cstdio>
#include <cstring>
using namespace std;
int key[2000005], na, nb, n;
char a[2000005], b[2000005];
int sol[1000000];
/*struct element
{
int inf;
element *urm;
element(int x = 0)
{
inf = x;
urm = NULL;
}
};
struct lista
{
element *root, *last;
}sol;
void push(lista &q, int val)
{
if(q.root == NULL)
{
q.root = new element(val);
q.last = q.root;
}
else
{
q.last -> urm = new element(val);
q.last = q.last -> urm;
}
}*/
void make_key()
{
int k = 0;
for(int i = 2; i < na; i++)
{
while(k>0 && a[i+1]!=a[k])
k = key[k];
if(a[k] == a[i])
k++;
key[i] = k;
}
}
void solve()
{
int k = 0;
for(int i = 0; i <= nb; i++)
{
while(k && b[i]!=a[k])
k = key[k-1];
if(a[k] == b[i])
k++;
if(k == na)
sol[n++] = i+1-na;
}
}
void afis()
{
printf("%d\n", n);
/*for(element *p = sol.root; p; p = p -> urm)
printf("%d ", p -> inf);
printf("\n");*/
for(int i = 0; i< n; i++)
printf("%d ", sol[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s\n", a, b);
na = strlen(a);
nb = strlen(b);
make_key();
solve();
afis();
return 0;
}