Pagini recente » Cod sursa (job #2087989) | Profil Clelia | Istoria paginii utilizator/velciu_ilinca | Cod sursa (job #149714) | Cod sursa (job #808640)
Cod sursa(job #808640)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int p, t;
int size;
int ans[2000002];
char P[2000002], T[2000002];
const int MOD1 = 100007;
const int MOD2 = 100021;
const int RADIX = 73;
int p1, p2, t1, t2;
int pow1 = 1, pow2 = 1;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", P, T);
p = strlen(P);
t = strlen(T);
if (p > t) {
printf("0");
return 0;
}
for (int i = 0; i < p; i++) {
p1 = (p1 * RADIX + P[i]) % MOD1;
p2 = (p2 * RADIX + P[i]) % MOD2;
t1 = (t1 * RADIX + T[i]) % MOD1;
t2 = (t2 * RADIX + T[i]) % MOD2;
if (i != 0) {
pow1 = (pow1 * RADIX) % MOD1;
pow2 = (pow2 * RADIX) % MOD2;
}
}
if (p1 == t1 && p2 == t2) {
ans[size++] = 0;
}
for (int i = p; i < t; i++) {
t1 = ((((t1 - T[i - p] * pow1) * RADIX + T[i]) % MOD1) + MOD1) % MOD1;
t2 = ((((t2 - T[i - p] * pow2) * RADIX + T[i]) % MOD2) + MOD2) % MOD2;
if (p1 == t1 && p2 == t2) {
ans[size++] = i - p + 1;
}
}
printf("%d\n", size);
for (int i = 0; i < min(size, 1000); i++) {
printf("%d ", ans[i]);
}
return 0;
}