Pagini recente » Cod sursa (job #3363141) | Cod sursa (job #3363170) | Cod sursa (job #3363148) | Cod sursa (job #3363181) | Cod sursa (job #3363199)
#include <stdio.h>
#define int long long
#define MAXN 2000000
#define MAXK 1000
int mod[2] = {1000000007, 1000000009}, b[2] = {67, 71}, putere[2];
int inv[MAXN + 1][2], h[MAXN + 1][2], rasp[MAXK + 1], hash[2];
int exp(int a, int n, int m) {
int t;
if (n == 0) {
return 1;
} else {
if (n % 2 == 1) {
return (a * exp(a, n - 1, m)) % mod[m];
} else {
t = exp(a, n / 2, m);
return (t * t) % mod[m];
}
}
}
static inline int conv(int ch) {
if ('a' <= ch && ch <= 'z') {
return ch - 'a' + 1;
} else if ('A' <= ch && ch <= 'Z') {
return ch - 'A' + 27;
} else if ('0' <= ch && ch <= '9') {
return ch - '0' + 53;
} else {
return 0;
}
}
static inline int get(int a, int b, int m) {
return (((h[b][m] - h[a - 1][m] + mod[m]) % mod[m]) * inv[a - 1][m]) % mod[m];
}
signed main() {
FILE *fin, *fout;
int n, m, k, ch, i, j;
for (i = 0; i < 2; i++) {
inv[MAXN][i] = exp(exp(b[i], MAXN, i), mod[i] - 2, i);
}
for (i = MAXN - 1; i >= 0; i--) {
for (j = 0; j < 2; j++) {
inv[i][j] = (inv[i + 1][j] * b[j]) % mod[j];
}
}
fin = fopen("strmatch.in", "r");
n = 0;
putere[0] = putere[1] = 1;
while ((ch = fgetc(fin)) != '\n') {
n++;
for (i = 0; i < 2; i++) {
hash[i] = (hash[i] + conv(ch) * putere[i]) % mod[i];
putere[i] = (putere[i] * b[i]) % mod[i];
}
}
m = 0;
putere[0] = putere[1] = 1;
while ((ch = fgetc(fin)) != '\n' && ch != EOF) {
m++;
for (i = 0; i < 2; i++) {
h[m][i] = (h[m - 1][i] + conv(ch) * putere[i]) % mod[i];
putere[i] = (putere[i] * b[i]) % mod[i];
}
}
fclose(fin);
k = 0;
i = 1;
while (i <= m - n + 1 && k <= MAXK) {
if (get(i, i + n - 1, 0) == hash[0] && get(i, i + n - 1, 1) == hash[1]) {
rasp[++k] = i;
}
i++;
}
fout = fopen("strmatch.out", "w");
fprintf(fout, "%lld\n", k);
for (i = 1; i <= k; i++) {
fprintf(fout, "%lld ", rasp[i] - 1);
}
fclose(fout);
return 0;
}