Pagini recente » Cod sursa (job #1506146) | Cod sursa (job #119338) | Cod sursa (job #154999) | Cod sursa (job #294999) | Cod sursa (job #1251481)
#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+1);
gets(b+1);
nr=strlen(a+1);
r=strlen(b+1);
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;
}