Pagini recente » Cod sursa (job #3363140) | Cod sursa (job #3363172) | Cod sursa (job #3363221) | Cod sursa (job #3363176) | Cod sursa (job #3363209)
#include <stdio.h>
#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 ((long long)a * exp(a, n - 1, m)) % mod[m];
} else {
t = exp(a, n / 2, m);
return ((long long)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 ((long long)(((long long)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] = ((long long)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] = ((long long)hash[i] + ((long long)conv(ch) * putere[i]) % mod[i]) % mod[i];
putere[i] = ((long long)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] = ((long long)h[m - 1][i] + ((long long)conv(ch) * putere[i]) % mod[i]) % mod[i];
putere[i] = ((long long)putere[i] * b[i]) % mod[i];
}
}
fclose(fin);
k = 0;
i = 1;
while (i <= m - n + 1) {
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, "%d\n", k);
for (i = 1; i <= ((k < MAXK) ? k : MAXK); i++) {
fprintf(fout, "%d ", rasp[i] - 1);
}
fclose(fout);
return 0;
}