Pagini recente » Cod sursa (job #331973) | Cod sursa (job #164335) | Cod sursa (job #729312) | Cod sursa (job #729716) | Cod sursa (job #856673)
Cod sursa(job #856673)
#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 * 73 + v[i] ) % mod1;
nrv2 = ( nrv2 * 73 + v[i] ) % mod2;
nrs1 = ( nrs1 * 73 + s[i] ) % mod1;
nrs2 = ( nrs2 * 73 + s[i] ) % mod2;
if(i)
{
p1 = ( p1 * 73 ) % mod1;
p2 = ( p2 * 73 ) % mod2;
}
}
if( nrv1 == nrs1 && nrv2 == nrs2)
poz[++npoz] = 0;
for(i = lv; i < ls; i++)
{
nrs1 = ( ( nrs1 - ( s[i-lv] * p1 ) % mod1 + mod1 ) * 73 + s[i] ) % mod1;
nrs2 = ( ( nrs2 - ( s[i-lv] * p2 ) % mod2 + mod2 ) * 73 + s[i] ) % mod2;
if( nrv1 == nrs1 && nrv2 == nrs2)
poz[++npoz] = i - lv + 1;
}
fprintf(g, "%d\n", npoz);
for( i = 1; i <= npoz && i<=1000; i++ )
fprintf(g, "%d ", poz[i]);
return 0;
}