Pagini recente » Monitorul de evaluare | Cod sursa (job #2099984) | Cod sursa (job #3343115) | Cod sursa (job #3357712) | Cod sursa (job #819722)
Cod sursa(job #819722)
#include <stdio.h>
#include<string.h>
#define mod1 666001
#define mod2 100007
using namespace std;
FILE *f = fopen("strmatch.in","r"), *g = fopen("strmatch.out","w");
char s[2000001], v[2000001];
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 + v[i] ) % mod1;
nrv2 = ( nrv2 * 256 + v[i] ) % mod2;
nrs1 = ( nrs1 * 256 + s[i] ) % mod1;
nrs2 = ( nrs2 * 256 + s[i] ) % mod2;
if(i)
{
p1 = ( p1 * 256 ) % mod1;
p2 = ( p2 * 256 ) % mod2;
}
}
for(i = lv; i < ls && npoz <= 1000; i++)
{
if( nrv1 == nrs1 && nrv2 == nrs2)
poz[++npoz] = i - lv;
nrs1 = ( ( ( nrs1 - ( s[i-lv] * p1 ) % mod1 ) * 256 ) + s[i] ) % mod1;
nrs2 = ( ( ( nrs2 - ( s[i-lv] * p2 ) % mod2 ) * 256 ) + s[i] ) % mod2;
}
fprintf(g, "%d\n", npoz);
for(i = 1; i <= npoz; i++)
fprintf(g, "%d ", poz[i]);
return 0;
}