Pagini recente » Cod sursa (job #2549581) | Cod sursa (job #452367) | Cod sursa (job #2731004) | Cod sursa (job #1546477) | Cod sursa (job #1251469)
#include <cstdio>
using namespace std;
int p1,p2,q1,q2,q11,q22,p11,p22,a[2000004],b[2000004],c[1004],nr,r,n,i,p;
char x;
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
scanf ("%c", &x);
while (x!='\n')
{
a[++nr]=int(x);
scanf ("%c", &x);
}
scanf ("%c", &x);
while (x!='\n')
{
b[++r]=int(x);
scanf ("%c", &x);
}
p=131;
p1=1;
p2=1;
for (i=1;i<=nr;i++)
{
q1*=p;
q1+=a[i];
q1%=666013;
q2*=p;
q2+=a[i];
q2%=10003;
q11*=p;
q11+=b[i];
q11%=666013;
q22*=p;
q22+=b[i];
q22%=10003;
if (i>1)
{
p1*=p;
p1%=666013;
p2*=p;
p2%=10003;
}
}
if (q11==q1 && q22==q2)
c[++n]=0;
for (i=nr+1;i<=r;i++)
{
q11-=(p1*b[i-nr]);
q22-=(p2*b[i-nr]);
q11%=666013;
q22%=10003;
if (q11<0)
q11+=666013;
if (q22<0)
q22+=10003;
q11*=p;
q11%=666013;
q22*=p;
q22%=10003;
q11+=b[i];
q22+=b[i];
q11%=666013;
q22%=10003;
if (q11==q1 && q22==q2)
{
if (n>=1000)
n++;
else
c[++n]=i-nr;
}
}
printf ("%d\n", n);
for (i=1;i<=n && i<=1000;i++)
printf ("%d ", c[i]);
return 0;
}