Pagini recente » Cod sursa (job #2909078) | Cod sursa (job #897954) | Cod sursa (job #2704781) | Cod sursa (job #354316) | Cod sursa (job #1325454)
#include<cstdio>
#define minim(a,b) ((a<b)?a:b)
int n,m;
char a[2000003],b[2000003];
int pi[2000003],pos[1024];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i,q=0,N=0;
gets(a);
gets(b);
for(;(a[m]>='A' && a[m]<='Z') || (a[m]>='a' && a[m]<='z') || (a[m]>='0' && a[m] <= '9');++m);
for(;(b[n]>='A' && b[n]<='Z') || (b[n] >= 'a' && b[n] <= 'z') || (b[n]>='0' && b[n]<='9');++n);
for(i=m;i;--i)
a[i]=a[i-1];
a[0]=' ';
for(i=n;i;--i)
b[i]=b[i-1];
b[0]=' ';
pi[1]=0;
for(i=2;i<=m;++i)
{
while(q && a[q+1]!=a[i])
q=pi[q];
if (a[q+1]==a[i])
++q;
pi[i]=q;
}
for(i=1;i<=n;++i)
{
while(q && a[q+1]!=b[i])
q=pi[q];
if (a[q+1]==b[i])
++q;
if (q==m)
{
q=pi[m];
++N;
if(N<=1000)
pos[N]=i-m;
}
}
printf("%d\n",N);
for (i=1;i<=minim(N,1000);++i)
printf("%d ", pos[i]);
printf("\n");
return 0;
}