Cod sursa(job #2750248)

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

#define LMAX 2000000
#define MOD1 1000003
#define MOD2 1000007

using namespace std;

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

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

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

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

    if(lgA > lgB){
        fout << 0;
        return 0;
    }

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

    int P1 = 1;
    int P2 = 1;
    for(int i = 1; i <= lgA - 1; i++){
        P1 = P1 * 27 % MOD1;
        P2 = P2 * 27 % MOD2;
    }

    int hash1 = 0;
    int hash2 = 0;
    for(int i = 0; i < lgA; i++){
        hash1 = (hash1 * 27 + b[i] - 'A' + 1) % MOD1;
        hash2 = (hash2 * 27 + b[i] - 'A' + 1) % MOD2;
    }

    if(hash1 == hashA1 && hash2 == hashA2){
        aparitii.push_back(0);
    }

    for(int i = lgA; i < lgB; i++){
        //sirul care se termina in i
        //acum il adaug pe i si il sterg pe j
        int j = i - lgA;

        hash1 = ( (MOD1 + hash1 - 1LL * (b[j] - 'A' + 1) * P1 % MOD1) % MOD1 * 27 + (b[i] - 'A' + 1) ) % MOD1;
        hash2 = ( (MOD2 + hash2 - 1LL * (b[j] - 'A' + 1) * P2 % MOD2) % MOD2 * 27 + (b[i] - 'A' + 1) ) % MOD2;

        /*
        cout << i << "\n";
        cout << "hash1 = " << hash1 << "\n";
        cout << "hash2 = " << hash2 << "\n";
        */

        if(hash1 == hashA1 && hash2 == hashA2){
            aparitii.push_back(j + 1);
        }
    }

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