Cod sursa(job #1413302)

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