Cod sursa(job #2556255)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 24 februarie 2020 19:39:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <cstring>
#define MOD1 100003
#define MOD2 100019
#define P 80

using namespace std;

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

int i, lg_a, lg_b, r[2000003];
int Hash_a1, Hash_a2, Hash1, Hash2, P1 = 1, P2 = 1;
char a[2000003], b[2000003];

int main()
{
    fin.getline ( a, 2000005 );
    fin.getline ( b, 2000005 );

    lg_a = strlen ( a );
    lg_b = strlen ( b );
    if ( lg_a > lg_b )
    {
        fout << 0;
        return 0;
    }

    for ( i = 0 ; i < lg_a ; i++ )
    {
        Hash_a1 = ( Hash_a1 * P + ( a[i] - '0' + 1 ) ) % MOD1;
        Hash_a2 = ( Hash_a2 * 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 ( Hash_a1 == Hash1 && Hash_a2 == Hash2 ) r[++r[0]] = 0;

    for ( i = lg_a ; i < lg_b ; i++ )
    {
        Hash1 = ( ( ( Hash1 - ( ( b[i-lg_a] - '0' + 1 ) * P1 ) % MOD1 + MOD1 ) * P ) % MOD1 + ( b[i] - '0' + 1 ) ) % MOD1;
        Hash2 = ( ( ( Hash2 - ( ( b[i-lg_a] - '0' + 1 ) * P2 ) % MOD2 + MOD2 ) * P ) % MOD2 + ( b[i] - '0' + 1 ) ) % MOD2;

        if ( Hash_a1 == Hash1 && Hash_a2 == Hash2 ) r[++r[0]] = i - lg_a + 1;
    }

    fout << r[0] << '\n';
    for ( i = 1 ; i <= r[0] ; i++ ) fout << r[i] << ' ';

    return 0;
}