Pagini recente » Romanii medaliati la IOI | Cod sursa (job #1664998) | Cod sursa (job #13) | Cod sursa (job #95340) | Cod sursa (job #530625)
Cod sursa(job #530625)
#include<cstdio>
#include<cstring>
using namespace std;
#define P 73
#define Prim1 100007
#define Prim2 100021
#define MAXS 200001
char A[MAXS], B[MAXS];
int Na, Nb;
int hash1, hash2, P1, P2;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", A, B);
Na = strlen(A);
Nb = strlen(B);
if (Na > Nb) {
printf("0\n");
return 0;
}
P1 = P2 = 1;
hash1 = hash2 = 0;
for (int i = 0; i < Na; i++) {
hash1 = (hash1 * P + A[i]) % Prim1;
hash2 = (hash2 * P + A[i]) % Prim2;
if (i) {
P1 = (P1 * P) % Prim1;
P2 = (P2 * P) % Prim2;
}
}
int hits[MAXS];
int N, auxH1, auxH2;
N = 0;
auxH1 = auxH2 = 0;
for (int i = 0; i < Na; i++) {
auxH1 = (auxH1 * P + B[i]) % Prim1;
auxH2 = (auxH2 * P + B[i]) % Prim2;
}
if (hash1 == auxH1 && hash2 == auxH2) hits[N++] = 1;
for (int i = Na; i < Nb; i++) {
auxH1 = ((auxH1 - (B[i-Na] * P1) % Prim1 + Prim1) * P + B[i]) % Prim1;
auxH2 = ((auxH2 - (B[i-Na] * P2) % Prim2 + Prim2) * P + B[i]) % Prim2;
if (hash1 == auxH1 && hash2 == auxH2) {
hits[i - Na + 1] = 1;
N++;
}
}
printf("%d\n", N);
N = 0;
for (int i = 0; i < Nb && N < 1000; i++){
if (hits[i] == 1) {
printf("%d ", i);
N++;
}
}
printf("\n");
return 0;
}