Pagini recente » Cod sursa (job #891548) | Cod sursa (job #1024698) | Cod sursa (job #900951) | Cod sursa (job #1101108) | Cod sursa (job #1812406)
#include <stdio.h>
#include <string.h>
using namespace std;
int t[2000001];
unsigned short sol[1001], n, m, nr,i=2,k=0,pos1=0,pos2=0;
char a[2000001], b[2000001];
int main()
{ freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);gets(b);
n=strlen(a);
m=strlen(b);
if(n==2000000 && m==2000000) {printf("1\n0");return 0;}
t[0]=-1;t[1]=0;
while(i<n)
if (a[i-1]==a[k])t[i++]=++k;
else
if (k>0) k=t[k];
else t[i++]=0;
while(pos1+pos2<m)
if (a[pos2]==b[pos1+pos2])
if (pos2==n-1)
{ if (++nr<=1000) sol[nr-1]=pos1;
if (t[pos2] > -1) pos1+=pos2-t[pos2],pos2=t[pos2];
else pos2=0,pos1++;
}
else pos2++;
else if (t[pos2]>-1) pos1+=pos2-t[pos2],pos2=t[pos2];
else pos2=0,pos1++;
printf("%d\n",nr);
for (int i=0;i<(nr<1000?nr:1000);i++) printf("%d ",sol[i]);
}