Pagini recente » Cod sursa (job #1535753) | Cod sursa (job #177412) | Cod sursa (job #1368766) | Cod sursa (job #2955956) | Cod sursa (job #1413261)
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define inFile "strmatch.in"
#define outFile "strmatch.out"
#define MAX_LEN 2000000
#define MAX_CHAR 255
#define MOD 1000003
#define MAX_MATCHES 1000
char A[MAX_LEN + 5];
char B[MAX_LEN + 5];
int chSum[MAX_LEN];
int chRank[MAX_CHAR];
int match[MAX_MATCHES];
int main() {
FILE *in = fopen(inFile, "r");
FILE *out = fopen(outFile, "w");
int lA, lB, i, j, alphPow = 1, chSum_A = 0, nMatches = 0;
const int alphabet = 62;
fgets(A, MAX_LEN + 4, in);
fgets(B, MAX_LEN + 4, in);
lA = strlen(A);
lB = strlen(B);
A[--lA] = 0;
B[--lB] = 0;
if(lA > lB) {
fprintf(out, "1\n0\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;
chSum[0] = chRank[B[0]];
chSum_A = chRank[A[0]];
for(i = 1; i < lA; i++) {
chSum[i] = (alphabet * chSum[i-1] + chRank[B[i]]) % MOD;
chSum_A = (alphabet * chSum_A + chRank[A[i]]) % MOD;
alphPow = (alphPow * alphabet) % MOD;
}
for(i = lA; i < lB; i++)
chSum[i] = (((chSum[i-1] - ((alphPow * chRank[B[i-lA]])%MOD) + MOD) % MOD) * alphabet + chRank[B[i]]) % MOD;
for(i = 0; i < lB; i++) {
if(chSum[i] == chSum_A) {
for(j = i-lA+1; j <= i && B[j] == A[j-i+lA-1]; j++);
if(j == i+1) {
if(nMatches < MAX_MATCHES)
match[nMatches] = i-lA+1;
nMatches++;
}
}
}
fprintf(out, "%d\n", nMatches);
for(i = 0; i < min(nMatches, MAX_MATCHES); i++)
fprintf(out, "%d ", match[i]);
return 0;
}