Cod sursa(job #1413261)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 1 aprilie 2015 19:22:49
Problema Potrivirea sirurilor Scor 66
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#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;
}