Pagini recente » Cod sursa (job #1005399) | Cod sursa (job #2884600) | Cod sursa (job #2151067) | Cod sursa (job #1488171) | Cod sursa (job #786413)
Cod sursa(job #786413)
#include <cassert>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2000005;
const int MOD = 666013;
const int BASE = 123;
char text[N], pattern[N];
int textHash, patternHash;
int sol[N], putere[N];
void read() {
assert(freopen("strmatch.in", "r", stdin) != NULL);
assert(freopen("strmatch.out", "w", stdout) != NULL);
assert(scanf("%s %s", pattern + 1, text + 1) == 2);
}
void solve() {
int n = strlen(pattern + 1);
int m = strlen(text + 1);
putere[0] = 1;
for (int i = 1; i < n; ++i)
putere[i] = (putere[i - 1] * BASE) % MOD;
for (int i = 1; i <= n; ++i)
patternHash = (patternHash + (pattern[i] * putere[n - i])) % MOD;
for (int i = 1; i <= n; ++i)
textHash = (textHash + (text[i] * putere[n - i])) % MOD;
int i = n;
while (i <= m) {
if (textHash == patternHash)
sol[++sol[0]] = i - n;
textHash = textHash - text[i - n + 1] * putere[n - 1];
textHash = (textHash % MOD + MOD) % MOD;
++i;
textHash = (textHash * BASE + text[i]) % MOD;
}
}
void write() {
int n = sol[0] <= 1000 ? sol[0] : 1000;
printf("%d\n", sol[0]);
for (int i = 1; i <= n; ++i)
printf("%d ", sol[i]);
}
int main() {
read();
solve();
write();
}