Pagini recente » Cod sursa (job #376558) | Cod sursa (job #706907) | Cod sursa (job #850947) | Cod sursa (job #1189206) | Cod sursa (job #1413302)
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
#define inFile "strmatch.in"
#define outFile "strmatch.out"
#define MAX_LEN 2000000
#define MAX_CHAR 255
#define MOD1 100007
#define MOD2 100021
#define MAX_MATCHES 1000
char A[MAX_LEN + 5];
char B[MAX_LEN + 5];
int chSum1[MAX_LEN];
int chSum2[MAX_LEN];
int chRank[MAX_CHAR];
int match[MAX_MATCHES];
int main() {
ifstream in(inFile);
ofstream out(outFile);
int lA, lB, i, j, alphPow1 = 1, alphPow2 = 1, chSum_A1, chSum_A2, nMatches = 0;
const int alphabet = 62;
in.getline(A, MAX_LEN + 5);
in.getline(B, MAX_LEN + 5);
lA = strlen(A);
lB = strlen(B);
if(lA > lB) {
out << 0 << '\n';
return 0;
}
for(i = 'A'; i <= 'Z'; i++)
chRank[i] = i - 'A';
for(i = 'a'; i <= 'z'; i++)
chRank[i] = i - 'a' + 26;
for(i = '0'; i <= '9'; i++)
chRank[i] = i - '0' + 52;
chSum1[0] = chRank[B[0]];
chSum2[0] = chRank[B[0]];
chSum_A1 = chRank[A[0]];
chSum_A2 = chRank[A[0]];
for(i = 1; i < lA; i++) {
chSum1[i] = (alphabet * chSum1[i-1] + chRank[B[i]]) % MOD1;
chSum2[i] = (alphabet * chSum2[i-1] + chRank[B[i]]) % MOD2;
chSum_A1 = (alphabet * chSum_A1 + chRank[A[i]]) % MOD1;
chSum_A2 = (alphabet * chSum_A2 + chRank[A[i]]) % MOD2;
alphPow1 = (alphPow1 * alphabet) % MOD1;
alphPow2 = (alphPow2 * alphabet) % MOD2;
}
for(i = lA; i < lB; i++) {
chSum1[i] = (((chSum1[i-1] - ((alphPow1 * chRank[B[i-lA]])%MOD1) + MOD1) % MOD1) * alphabet + chRank[B[i]]) % MOD1;
chSum2[i] = (((chSum2[i-1] - ((alphPow2 * chRank[B[i-lA]])%MOD2) + MOD2) % MOD2) * alphabet + chRank[B[i]]) % MOD2;
}
for(i = lA-1; i < lB; i++) {
if(chSum_A1 == chSum1[i] && chSum_A2 == chSum2[i]) {
if(nMatches < MAX_MATCHES)
match[nMatches] = i-lA+1;
nMatches++;
}
}
out << nMatches <<'\n';
for(i = 0; i < min(nMatches, MAX_MATCHES); i++)
out << match[i] << ' ';
return 0;
}