Pagini recente » Cod sursa (job #47902) | Cod sursa (job #1839422) | Cod sursa (job #1798605) | Cod sursa (job #2979338) | Cod sursa (job #530623)
Cod sursa(job #530623)
#include<cstdio>
#include<cstring>
using namespace std;
#define base 101
#define Prim1 100007
#define Prim2 104729
#define MAXS 2000001
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 * base + A[i]) % Prim1;
hash2 = (hash2 * base + A[i]) % Prim2;
if (i) {
P1 = (P1 * base) % Prim1;
P2 = (P2 * base) % Prim2;
}
}
int hits[MAXS];
int N, auxH1, auxH2;
N = 0;
auxH1 = auxH2 = 0;
for (int i = 0; i < Na; i++) {
auxH1 = (auxH1 * base + B[i]) % Prim1;
auxH2 = (auxH2 * base + 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) * base + B[i]) % Prim1;
auxH2 = ((auxH2 - (B[i-Na] * P2) % Prim2 + Prim2) * base + B[i]) % Prim2;
if (hash1 == auxH1 && hash2 == auxH2) hits[N++] = i+1;
}
printf("%d\n", N);
for (int i = 0; i < N; i++)
printf("%d ", hits[i] - Na);
printf("\n");
return 0;
}