Cod sursa(job #2572994)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 5 martie 2020 15:20:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
#define LGMAX 2000005
#define MOD1 45007
#define MOD2 45013
#define P 80

using namespace std;

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

vector < int > R;
char a[LGMAX], b[LGMAX];

int main()
{
    int lg_a, lg_b, i, hash1a = 0, hash2a = 0, hash1 = 0, hash2 = 0, P1 = 1, P2 = 1, nr;

    fin.getline ( a, LGMAX );
    fin.getline ( b, LGMAX );
    lg_a = strlen ( a );
    lg_b = strlen ( b );

    if ( lg_a > lg_b )
    {
        fout << 0;
        return 0;
    }

    for ( i = 0 ; i < lg_a ; i++ )
    {
        hash1a = ( hash1a * P + a[i] - '0' + 1 ) % MOD1;
        hash2a = ( hash2a * P + a[i] - '0' + 1 ) % MOD2;

        hash1 = ( hash1 * P + b[i] - '0' + 1 ) % MOD1;
        hash2 = ( hash2 * P + b[i] - '0' + 1 ) % MOD2;

        if ( i != 0 ) P1 = ( P1 * P ) % MOD1, P2 = ( P2 * P ) % MOD2;
    }

    if ( hash1a == hash1 && hash2a == hash2 ) R.push_back ( 0 );
    for ( i = lg_a ; i < lg_b ; i++ )
    {
        hash1 = ( ( hash1 - ( P1 * ( b[i-lg_a] - '0' + 1 ) ) % MOD1 + MOD1 ) * P + b[i] - '0' + 1 ) % MOD1;
        hash2 = ( ( hash2 - ( P2 * ( b[i-lg_a] - '0' + 1 ) ) % MOD2 + MOD2 ) * P + b[i] - '0' + 1 ) % MOD2;

        if ( hash1 == hash1a && hash2 == hash2a ) R.push_back ( i - lg_a + 1 );
    }

    fout << R.size() << '\n';
    nr = R.size();
    nr = min ( nr, 1000 );
    for ( i = 0 ; i < nr ; i++ ) fout << R[i] << ' ';

    return 0;
}