Pagini recente » Cod sursa (job #1887476) | Cod sursa (job #1477768) | Cod sursa (job #290816) | Borderou de evaluare (job #366934) | Cod sursa (job #2678239)
#include <cstdio>
#include <cstring>
#define MAXN 2000005
#define D 73
#define MOD1 100007
#define MOD2 100021
char a[MAXN], b[MAXN];
int nrla, nrlb, hashA1, hashA2, P1 = 1, P2 = 1, hash1, hash2, nr_pot;
bool match[MAXN];
void citire() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", a, b);
nrla = strlen(a);
nrlb = strlen(b);
}
void initializare() {
for (int i = 0; i < nrla; ++i) {
hashA1 = (hashA1 * D + a[i]) % MOD1;
hashA2 = (hashA2 * D + a[i]) % MOD2;
if (i != 0) {
P1 = (P1 * D) % MOD1;
P2 = (P2 * D) % MOD2;
}
}
for (int i = 0; i < nrla; ++i) {
hash1 = (hash1 * D + b[i]) % MOD1;
hash2 = (hash2 * D + b[i]) % MOD2;
}
}
void cautare_potriviri() {
if (hash1 == hashA1 && hash2 == hashA2) {
match[0] = true;
nr_pot++;
}
for (int i = nrla; i < nrlb; ++i) {
hash1 = ((hash1 - (b[i - nrla] * P1) % MOD1 + MOD1) * D + b[i]) % MOD1;
hash2 = ((hash2 - (b[i - nrla] * P2) % MOD2 + MOD2) * D + b[i]) % MOD2;
if (hash1 == hashA1 && hash2 == hashA2) {
match[i - nrla + 1] = true;
nr_pot++;
}
}
}
void afisare() {
printf("%d\n", nr_pot);
nr_pot = 0;
for (int i = 0; i < nrlb && nr_pot < 1000; ++i)
if (match[i]) {
nr_pot++;
printf("%d ", i);
}
}
int main() {
citire();
if (nrla > nrlb) {
printf("0");
return 0;
}
initializare();
cautare_potriviri();
afisare();
return 0;
}