Cod sursa(job #2572792)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 5 martie 2020 14:21:20
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
#define LGMAX 200005
#define MOD1 45007
#define MOD2 45013
#define P 60

using namespace std;

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

int R[LGMAX];

int main()
{
    int lg_a, lg_b, i, hash1a = 0, hash2a = 0, hash1 = 0, hash2 = 0, P1 = 1, P2 = 1, nr = 0;
    char a[LGMAX], b[LGMAX];

    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 ) % MOD1 ) + ( a[i] - 'A' + 1 ) ) % MOD1;
        hash2a = ( ( ( hash2a * P ) % MOD2 ) + ( a[i] - 'A' + 1 ) ) % MOD2;

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

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

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

        if ( hash1 == hash1a && hash2 == hash2a ) R[++nr] = i - lg_a + 1;
    }

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

    return 0;
}