Pagini recente » Istoria paginii utilizator/pupiraresdi | Monitorul de evaluare | Istoria paginii utilizator/8claudiac65100wr5 | Istoria paginii utilizator/bmanghiuc | Cod sursa (job #2001444)
#include <bits/stdc++.h>
using namespace std;
FILE *F=fopen("strmatch.in", "r"), *G=fopen("strmatch.out", "w");
int p1, p2, na, nb, hsh1, hsh2, hsha1, hsha2, nr;
char b[2000003], a[2000003];
bitset<2000003> mtch;
const int MOD1 = 100007;
const int MOD2 = 100021;
const int p = 73;
int main()
{
fscanf(F, "%s %s", &a, &b);
na = strlen(a);
nb = strlen(b);
if(na > nb)
{
fprintf(G, "%d", 0);
return 0;
}
p1 = 1; p2 = 1;
hsha1=(hsha1 * p + a[0])%MOD1,
hsha2=(hsha2 * p + a[0])%MOD2;
for(int i = 1; i < na; ++ i)
hsha1=(hsha1 * p + a[i])%MOD1,
hsha2=(hsha2 * p + a[i])%MOD2,
p1 = (p * p1)%MOD1,
p2 = (p * p2)%MOD2;
for(int i = 0; i < na; ++ i)
hsh1=(hsh1 * p + b[i])%MOD1,
hsh2=(hsh2 * p + b[i])%MOD2;
if(hsh1 == hsha1 && hsh2 == hsha2)
nr++, mtch[0] = 1;
for(int i = na; i < nb; ++ i)
{
hsh1 = ((hsh1 - (b[i-na]*p1)%MOD1 + MOD1)* p + b[i])%MOD1;
hsh2 = ((hsh2 - (b[i-na]*p2)%MOD2 + MOD2)* p + b[i])%MOD2;
if(hsh1 == hsha1 && hsh2 == hsha2)
mtch[i-na+1] = 1, ++ nr;
}
fprintf(G, "%d\n", nr);
nr = 0;
for(int i = 0; i < nb && nr < 1000; ++ i)
if(mtch[i]) ++nr, fprintf(G, "%d ", i);
return 0;
}