Pagini recente » Cod sursa (job #308504) | Cod sursa (job #1896611) | Cod sursa (job #2325978) | Cod sursa (job #2160395) | Cod sursa (job #1251470)
#include <cstdio>
#include <cstring>
using namespace std;
int p1,p2,q1,q2,q11,q22,p11,p22,c[1004],nr,r,n,i,p;
char x,a[2000004],b[2000004];
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
gets(a);
gets(b);
nr=strlen(a);
r=strlen(b);
p=131;
p1=1;
p2=1;
for (i=1;i<=nr;i++)
{
q1*=p;
q1+=int(a[i]);
q1%=666013;
q2*=p;
q2+=int(a[i]);
q2%=10003;
q11*=p;
q11+=int(b[i]);
q11%=666013;
q22*=p;
q22+=int(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*int(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+=int(b[i]);
q22+=int(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;
}