Pagini recente » Cod sursa (job #2565712) | Cod sursa (job #2891005) | Cod sursa (job #2304447) | Cod sursa (job #2839252) | Cod sursa (job #938809)
Cod sursa(job #938809)
#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)
{
sol[++s]=i-n;
if (s>1000)
{
s=1000;
i=m+1;
}
}
}
}
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));
for (i=1; i<s+1; ++i)
assert(printf("%d ",sol[i]));
assert(printf("\n"));
return 0;
}