Pagini recente » Cod sursa (job #431480) | Cod sursa (job #2077013) | Cod sursa (job #1312255) | Cod sursa (job #736960) | Cod sursa (job #1278731)
#include <cstdio>
#include <cstring>
using namespace std;
FILE *fin, *fout;
#define NMAX 2000001
#define MOD1 100007
#define MOD2 100021
#define P 73
char A[NMAX], B[NMAX];
int main() {
fin = fopen ("strmatch.in", "r");
fout = fopen ("strmatch.out", "w");
int i, la, lb;
int hashA1=0, hashA2=0, hashB1=0, hashB2=0, P1 = 1, P2 = 1;
int matches = 0, match[NMAX];
fscanf (fin, "%s%s", A, B);
la = strlen(A); lb = strlen(B);
if (la > lb) {
fprintf(fout, "0\n");
return 0;
}
for (i=0; i<la; ++i) {
hashA1 = (P * hashA1 + A[i]) % MOD1;
hashA2 = (P * hashA2 + A[i]) % MOD2;
hashB1 = (P * hashB1 + B[i]) % MOD1;
hashB2 = (P * hashB2 + B[i]) % MOD2;
if (i) {
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
if (hashA1 == hashB1 && hashA2 == hashB2) match[++matches] = 0;
for (i=la; i<lb; ++i) {
hashB1 = (((hashB1 - P1 * B[i-la]) % MOD1 + MOD1) * P + B[i]) % MOD1;
hashB2 = (((hashB2 - P2 * B[i-la]) % MOD2 + MOD2) * P + B[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2) match[++matches] = i - la + 1;
}
fprintf (fout, "%d\n", matches);
la = (matches < 1000)?matches:1000;
for (i=1; i<=la; ++i) fprintf (fout, "%d ", match[i]);
fclose(fin); fclose(fout);
return 0;
}