Pagini recente » Cod sursa (job #2738688) | Cod sursa (job #2022780) | Cod sursa (job #3140226) | Istoria paginii utilizator/dianaluta | Cod sursa (job #1982192)
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 100003;
const int MOD2 = 100043;
const int MAXL = 2000010;
const int ORI = 73;
char s1[MAXL], s2[MAXL], pot[MAXL];
int main()
{
FILE *fin, *fout;
int n1, n2, hh1, hh2, p1, p2, i, h1, h2, nr;
fin = fopen ("strmatch.in", "r");
fout = fopen ("strmatch.out", "w");
fscanf (fin, "%s", &s1);
n1 = strlen (s1);
fscanf (fin, "%s", &s2);
n2 = strlen (s2);
hh1 = hh2 = 0;
p1 = p2 = 1;
for (i = 0; i < n1; i++) {
hh1 = (hh1 * ORI + s1[i] - '0') % MOD1;
hh2 = (hh2 * ORI + s1[i] - '0') % MOD2;
if (i > 0) {
p1 = (p1 * ORI) % MOD1;
p2 = (p2 * ORI) % MOD2;
}
}
h1 = h2 = 0;
for (i = 0; i < n1; i++) {
h1 = (h1 * ORI + s2[i] - '0') % MOD1,
h2 = (h2 * ORI + s2[i] - '0') % MOD2;
}
nr = 0;
if (hh1 == h1 && hh2 == h2) {
pot[0] = 1;
nr++;
}
for (i = n1; i < n2; i++) {
h1 = ((h1 - ((s2[i - n1] - '0') * p1) % MOD1 + MOD1) * ORI + s2[i] - '0') % MOD1;
h2 = ((h2 - ((s2[i - n1] - '0') * p2) % MOD2 + MOD2) * ORI + s2[i] - '0') % MOD2;
if (h1 == hh1 && h2 == hh2) {
pot[ i - n1 + 1 ] = 1;
nr++;
}
}
fprintf (fout, "%d\n", nr);
nr = 0;
for (i = 0; i < n2 && nr < 1000; i++)
if (pot[i] == 1) {
fprintf (fout, "%d ", i);
nr++;
}
fclose (fin);
fclose (fout);
return 0;
}