Pagini recente » Borderou de evaluare (job #3363142) | Borderou de evaluare (job #3363201) | Borderou de evaluare (job #3363151) | Borderou de evaluare (job #3363166) | Cod sursa (job #3363167)
#include <stdio.h>
#define int long long
#define MAXN 2000000
#define MAXK 1000
#define MOD 1000000007
#define B 67
int inv[MAXN + 1], h[MAXN + 1], rasp[MAXK + 1];
int exp(int a, int n) {
int t;
if (n == 0) {
return 1;
} else {
if (n % 2 == 1) {
return (a * exp(a, n - 1)) % MOD;
} else {
t = exp(a, n / 2);
return (t * t) % MOD;
}
}
}
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) {
return (((h[b] - h[a - 1] + MOD) % MOD) * inv[a - 1]) % MOD;
}
signed main() {
FILE *fin, *fout;
int n, m, k, hash, pow, ch, i;
inv[MAXN] = exp(exp(B, MAXN), MOD - 2);
for (i = MAXN - 1; i >= 0; i--) {
inv[i] = (inv[i + 1] * B) % MOD;
}
fin = fopen("strmatch.in", "r");
n = hash = 0;
pow = 1;
while ((ch = fgetc(fin)) != '\n') {
n++;
hash = (hash + conv(ch) * pow) % MOD;
pow = (pow * B) % MOD;
}
m = 0;
pow = 1;
while ((ch = fgetc(fin)) != '\n' && ch != EOF) {
m++;
h[m] = (h[m - 1] + conv(ch) * pow) % MOD;
pow = (pow * B) % MOD;
}
fclose(fin);
k = 0;
i = 1;
while (i <= m - n + 1 && k <= MAXK) {
if (get(i, i + n - 1) == hash) {
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;
}