Pagini recente » Clasament time_ | Cod sursa (job #2021479) | Istoria paginii preoni-2008/clasament/runda-finala/10 | Formatare Textile | Cod sursa (job #856871)
Cod sursa(job #856871)
#include <cstdio>
#include <cstring>
using namespace std;
#define nmax 2000001
#define baza 141
#define mod1 100007
#define mod2 100021
char a[nmax], b[nmax];
int m, n;
int h1, h2, pmax1, pmax2;
int gasit[nmax], k;
int main()
{
int i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s",&a,&b);
n=strlen(a);
m=strlen(b);
if (n>m) { printf("0\n"); return 0;}
pmax1=pmax2=1;
h1=h2=0;
for (i=0;i<n;++i)
{
h1=(h1*baza+a[i])%mod1;
h2=(h2*baza+a[i])%mod2;
if (i>0)
{ pmax1=(pmax1*baza)%mod1;
pmax2=(pmax2*baza)%mod2;}
}
int hb1=0,hb2=0;
for (i=0;i<n;++i)
{ hb1=(hb1*baza+b[i])%mod1;
hb2=(hb2*baza+b[i])%mod2;}
int nrgasit=0;
if (h1==hb1&&h2==hb2)
gasit[++k] = 0;
for (i=n;i<m;++i)
{
hb1=((hb1-(b[i-n]*pmax1)%mod1+mod1)*baza+b[i])%mod1;
hb2=((hb2-(b[i-n]*pmax2)%mod2+mod2)*baza+b[i])%mod2;
if (h1==hb1&&h2==hb2)
gasit[++k] = i-n+1;
}
printf("%d\n", k);
for (i=1; i<=k && i<=1000; ++i)
printf("%d ", gasit[i]);
return 0;
}