Pagini recente » Monitorul de evaluare | Cod sursa (job #3333838) | Monitorul de evaluare | Cod sursa (job #2482964) | Cod sursa (job #819700)
Cod sursa(job #819700)
#include <stdio.h>
#include<string.h>
#define mod1 666001
#define mod2 1002341
using namespace std;
FILE *f=fopen("strmatch.in","r"), *g=fopen("strtmach.out","w");
char s[2000001], v[2000001];
long long int i, j, nrv1=0, nrs1=0, nrv2=0, nrs2=0, p1=1, p2=1, lv, ls, poz[2000001], npoz=0;
int main()
{
fscanf(f, "%s%s", &v, &s);
lv=strlen(v);
ls=strlen(s);
for(i=0;i<lv;i++)
{
nrv1=((nrv1*256)%mod1+v[i])%mod1;
nrv2=((nrv2*256)%mod2+v[i])%mod2;
}
for(i=0;i<lv;i++)
{
nrs1=((nrs1*256)%mod1+s[i])%mod1;
nrs2=((nrs2*256)%mod2+s[i])%mod2;
}
if(nrv1==nrs1&&nrv2==nrs2)
poz[++npoz]=0;
for(i=1;i<=lv-1;i++)
{
p1=(p1*256)%mod1;
p2=(p2*256)%mod2;
}
for(i=lv; i<ls && npoz<=1000; i++)
{
nrs1=(((nrs1-(s[i-lv]*p1)%mod1)*256)%mod1+s[i])%mod1;
nrs2=(((nrs2-(s[i-lv]*p2)%mod2)*256)%mod2+s[i])%mod2;
if(nrv1==nrs1 && nrv2==nrs2)
poz[++npoz]=i-lv+1;
}
fprintf(g, "%lld\n", npoz);
for(i=1;i<=npoz;i++)
fprintf(g, "%lld ", poz[i]);
return 0;
}