Cod sursa(job #2750239)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 10 mai 2021 12:47:09
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

#define MOD1 1000003
#define LMAX 2000000

using namespace std;

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

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

int putere(int b, int e, int MOD){
    if(e == 0){
        return 1;
    }
    if(e % 2 == 0){
        return putere(1LL * b * b % MOD, e / 2, MOD);
    }
    return 1LL * b * putere(1LL * b * b % MOD, e / 2, MOD) % MOD;
}

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

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

    //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 HashAux;
        if(j > 0){
            HashAux = ( MOD1 + sumP[i] - ( 1LL * sumP[j - 1] * putere(27, i - j + 1, MOD1) % MOD1 ) ) % MOD1;
        }
        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;
}