Pagini recente » Cod sursa (job #2296677) | Cod sursa (job #2055348) | Cod sursa (job #1915766) | Cod sursa (job #835950) | Cod sursa (job #557047)
Cod sursa(job #557047)
#include <cstdio>
#include <string>
#include <cstring>
#define B1 29
#define B2 73
#define m1 666013
#define m2 100007
#define maxn 2000010
using namespace std;
int N, M, hash1, hash2, H1, H2, nr;
bool m[maxn];
char A[maxn], B[maxn];
int main ()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
int i, j, p1, p2;
scanf ("%s\n%s\n", A + 1, B + 1);
N = strlen (A + 1);
M = strlen (B + 1);
if (N > M) {
printf ("0\n");
return 0;
}
p1 = p2 = 1;
for (i = 1; i <= N; i++) {
hash1 = (hash1 * B1 + A[i]) % m1;
hash2 = (hash2 * B2 + A[i]) % m2;
if (i != 1) {
p1 = (p1 * B1) % m1;
p2 = (p2 * B2) % m2;
}
}
for (i = 1; i <= N; i++) {
H1 = (H1 * B1 + B[i]) % m1;
H2 = (H2 * B2 + B[i]) % m2;
}
if (hash1 == H1 && hash2 == H2) {
++nr;
m[1] = 1;
}
for (i = N + 1; i <= M; i++) {
H1 = ((H1 - (B[i - N] * p1) % m1 + m1) * B1 + B[i]) % m1;
H2 = ((H2 - (B[i - N] * p2) % m2 + m2) * B2 + B[i]) % m2;
if (H1 == hash1 && H2 == hash2) {
++nr;
m[i - N + 1] = 1;
}
}
printf ("%d\n", nr);
for (j = 1, i = 1; i <= M && j <= 1000; i++)
if (m[i]) {
printf ("%d ", i - 1);
++j;
}
return 0;
}