Cod sursa(job #2750247)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 10 mai 2021 13:11:25
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

#define MOD1 1000003
#define MOD2 1000007

#define LMAX 2000000

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int putere[LMAX + 1];
int sumP[LMAX + 1];
char a[LMAX + 1], b[LMAX + 1];
vector <int> aparitii;

void precalcularePuteri(){
    putere[0] = 1;
    for(int i = 1; i <= LMAX; i++){
        putere[i] = 1LL * putere[i - 1] * 27 % MOD1;
    }
}

int main()
{
    fin.getline(a, LMAX + 1);
    fin.getline(b, LMAX + 1);

    int lgA = strlen(a);
    int lgB = strlen(b);

    precalcularePuteri();

    //calculez Hash
    int Hash = 0;
    for(int i = 0; i < lgA; i++){
        Hash = ( Hash * 27 + a[i] - 'A' + 1 ) % MOD1;
    }

    sumP[0] = (b[0] - 'A' + 1) % MOD1;
    for(int i = 1; i < lgB; i++){
        sumP[i] = (sumP[i - 1] * 27 + b[i] - 'A' + 1) % MOD1;
    }

    /*
    cout << "Hash = " << Hash << "\n";
    for(int i = 0; i < lgB; i++){
        cout << i << " : " << sumP[i] << "\n";
    }
    cout << "\n";
    */

    for(int i = lgA - 1; i < lgB; i++){
        //verific daca sirul care se termina in i este subsecventa
        int j = i - lgA + 1;
        int HashAux1;
        int HashAux2;

        if(j > 0){
            HashAux1 = ( MOD1 + sumP[i] - ( 1LL * sumP[j - 1] * putere[i - j + 1] % MOD1 ) ) % MOD1;
            HashAux2 = ( MOD2 + sumP[i] - ( 1LL * sumP[j - 1] * putere[i - j + 1] % MOD2 ) ) % MOD2;
        }
        else {
            HashAux = sumP[i];
        }

        if(HashAux == Hash){
            aparitii.push_back(j);
        }

        /*
        cout << j << ' ' << i << "\n";
        cout << HashAux << "\n";
        cout << "\n";
        */

    }

    fout << aparitii.size() << "\n";
    for(int i = 0; i < aparitii.size(); i++){
        fout << aparitii[i] << ' ';
    }

    return 0;
}