Pagini recente » Cod sursa (job #2872158) | Cod sursa (job #2154179) | Cod sursa (job #249176) | Cod sursa (job #1405935) | Cod sursa (job #938812)
Cod sursa(job #938812)
#include <cassert>
#include <cstdio>
#include <cstring>
const int nmax=2000010;
int p[nmax],sol[1010];
int n=0,m=0,i=0,k=0,s=0;
char a[nmax],b[nmax];
void prefix()
{
p[1]=0;
for (i=2; i<n+1; ++i)
{
while (k>0 && a[k+1]!=a[i])
k=p[k];
if (a[k+1]==a[i])
++k;
p[i]=k;
}
}
void x()
{
for (i=1; i<m+1; ++i)
{
while (k>0 && a[k+1]!=b[i])
k=p[k];
if (a[k+1]==b[i])
++k;
if (n==k)
{
if (s<1001)
sol[++s]=i-n;
else
++s;
}
}
}
int main()
{
assert(freopen("strmatch.in","r",stdin));
assert(freopen("strmatch.out","w",stdout));
assert(scanf("%s%s",a+1,b+1));
n=strlen(a+1);
m=strlen(b+1);
prefix();
x();
if (s>1000)
assert(printf("1000\n"));
else
assert(printf("%d\n",s));
if (s<1001)
for (i=1; i<s+1; ++i)
assert(printf("%d ",sol[i]));
else
for (i=1; i<1001; ++i)
assert(printf("%d ",sol[i]));
assert(printf("\n"));
return 0;
}