Pagini recente » Cod sursa (job #1029420) | Cod sursa (job #1412614) | Cod sursa (job #1711530) | Cod sursa (job #1771972) | Cod sursa (job #144667)
Cod sursa(job #144667)
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
const int Factor = 73;
const int Mod1 = 100007;
const int Mod2 = 100021;
char P[2000001],
T[2000001];
int matched[2000001],
mn(0);
FILE *fout;
void rkmatch() {
int M = strlen(P),
N = strlen(T);
if (M > N) {
fprintf(fout, "0\n");
return;
}
int ps1(0),
ps2(0);
for (int i(0); i < M; ++i) {
ps1 = (ps1 * Factor + P[i]) % Mod1;
ps2 = (ps2 * Factor + P[i]) % Mod2;
}
//cout << ps1 << " - " << ps2 << endl;
int raisedFactor1(1),
raisedFactor2(1);
for (int i(0); i < M - 1; ++i) {
raisedFactor1 = (raisedFactor1 * Factor) % Mod1;
raisedFactor2 = (raisedFactor2 * Factor) % Mod2;
}
int check1(0),
check2(0);
int i(0);
for (; i < M; ++i) {
check1 = (check1 * Factor + T[i]) % Mod1;
check2 = (check2 * Factor + T[i]) % Mod2;
}
if ((check1 == ps1) && (check2 == ps2))
matched[mn++] = 0;
for (; i < N; ++i) {
check1 = ((check1 - (T[i-M]*raisedFactor1) % Mod1 + Mod1) * Factor + T[i]) % Mod1;
check2 = ((check2 - (T[i-M]*raisedFactor2) % Mod2 + Mod2) * Factor + T[i]) % Mod2;
//cout << check1 << " - " << check2 << endl;
if ((check1 == ps1) && (check2 == ps2))
matched[mn++] = i - M + 1;
}
fprintf(fout, "%d\n", mn);
for (i = 0; i < ((mn > 1000) ? (1000) : (mn)); ++i)
fprintf(fout, "%d ", matched[i]);
fprintf(fout, "\n");
}
int main(int argc, char *argv[]) {
FILE *fin = fopen("strmatch.in", "r");
fscanf(fin, "%s", P);
fscanf(fin, "%s", T);
fclose(fin);
fout = fopen("strmatch.out", "w");
rkmatch();
fclose(fout);
return 0;
}