Cod sursa(job #411851)
#include <stdio.h>
#include <string.h>
#define size 2000010
using namespace std;
char S1[size],S2[size];
int *poz;
int rez[1005];
int nr,lg1,lg2;
void citire()
{
fgets(S1+1,size,stdin);
S1[strlen(S1+1)]=0;
fgets(S2+1,size,stdin);
S2[strlen(S2+1)]=0;
lg1=strlen(S1+1);
lg2=strlen(S2+1);
poz = new int[lg1+2];
}
void prefix()
{
int k=0;
poz[0]=poz[1]=0;
for (int i=2;i<=lg1;i++)
{
while (k!=0 && S1[i]!=S1[k+1])
k=poz[k];
if (S1[i]==S1[k+1])
k++;
poz[i]=k;
}
}
void solve()
{
int k=0;
for (int j=1;j<=lg2;j++)
{
while (k!=0 && S2[j]!=S1[k+1])
k=poz[k];
if (S2[j]==S1[k+1])
k++;
if (k==lg1)
{
if (nr<1000)
rez[nr]=j;
nr++;
k=poz[k];
}
}
printf("%d\n",nr);
if (nr>1000)
nr=1000;
for (int i=0;i<nr;i++)
printf("%d ",rez[i]-lg1);
}
int main ()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
citire();
prefix();
solve();
return 0;
}