Pagini recente » Cod sursa (job #333842) | Cod sursa (job #606473) | Cod sursa (job #2164025) | Cod sursa (job #1826566) | Cod sursa (job #558317)
Cod sursa(job #558317)
#include <cstdio>
#include <cstring>
#define NMAX 2000050
#define P 56
bool V[NMAX];
char A[NMAX], B[NMAX];
short int HA2, HB2, P2;
int HA1, HB1, P1, nr, n, m, i;
int main () {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
scanf ("%s\n%s", A, B);
n = strlen (A), m = strlen (B);
P1 = P2 = 1;
for (i = 0; i < n; i++) {
HA1 = HA1 * P + A[i];
HA2 = HA2 * P + A[i];
HB1 = HB1 * P + B[i];
HB2 = HB2 * P + B[i];
if (i > 0)
P1 = P1 * P, P2 = P2 * P;
}
if (HA1 == HB1 && HA2 == HB2)
nr++, V[0] = 1;
for (i = n; i < m; i++) {
HB1 = (HB1 - P1 * B[i - n]) * P + B[i];
HB2 = (HB2 - P2 * B[i - n]) * P + B[i];
if (HA1 == HB1) //&& HA2 == HB2)
nr++, V[i - n + 1] = 1;
}
printf ("%d\n", nr);
nr = 0;
for (i = 0; i < m && nr < 1000; i++)
if (V[i]) {
nr++;
printf ("%d ", i);
}
return 0;
}