Cod sursa(job #2842543)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 1 februarie 2022 09:58:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <fstream>

using namespace std;

ifstream cin ( "strmatch.in" );
ofstream cout ( "strmatch.out" );

#define MOD1 666013
#define MOD2 781423
#define BAZA 32
#define NMAX 1000

#define int long long

int pozitii_ans[NMAX];

int lg_put( int base, int power, int MOD ) {
    int answer;
    answer = 1;
    while ( power > 0 ) {
        if ( power % 2 == 1 )
            answer = ( answer * base ) % MOD;
        base = ( base * base ) % MOD;
        power = power / 2;
    }
    return answer;
}

int code_hash( string& s, int size, int MOD ) {
    int code, i;

    code = 0;
    for ( i = 0; i < size; i++ )
        code = ( code * BAZA + s[i] ) % MOD;

    return code;
}

int add_hash_character( int code, char ch, int MOD ) {
    return ( code * BAZA + ch ) % MOD;
}

int remove_first_character( int code, char ch, int pow, int MOD ) {
    code -= ch * pow % MOD;
    if ( code < 0 )
        code += MOD;
    return code;
}

bool check( string& a, string& b, int poz ) {
    int i;
    i = 0;
    while ( i < b.size() && i + poz < a.size() && a[i + poz] == b[i] ) {
        i++;
    }
    return i == b.size();
}

int search( string& query, string& pattern ) {
    int code_query, code_pattern, pow, pow1, i, ans, code_pattern_1, code_query_1;
    code_query = code_hash( query, pattern.size() - 1, MOD1 );
    code_query_1 = code_hash( query, pattern.size() - 1, MOD2 );
    code_pattern = code_hash( pattern, pattern.size(), MOD1 );
    code_pattern_1 = code_hash( pattern, pattern.size(), MOD2 );
    pow = lg_put( BAZA, pattern.size() - 1, MOD1 );
    pow1 = lg_put( BAZA, pattern.size() - 1, MOD2 );
    ans = 0;
    i = pattern.size() - 1;
    while ( i < query.size() ) {
        code_query = add_hash_character(code_query, query[i], MOD1);
        code_query_1 = add_hash_character( code_query_1, query[i], MOD2 );
        if ( code_pattern == code_query && code_pattern_1 == code_query_1 ) {
            if ( ans < NMAX ) {
                pozitii_ans[ans++] = i;
            }
            else
                ans++;
        }
        code_query = remove_first_character( code_query, query[i - pattern.size() + 1], pow, MOD1 );
        code_query_1 = remove_first_character( code_query_1, query[i - pattern.size() + 1], pow1, MOD2 );
        i++;
    }
    return ans;
}

signed main() {
    string a, b;
    int i, ans;
    cin >> a >> b;
    ans = search( b, a );
    cout << ans << "\n";
    for ( i = 0; i < ans && i < NMAX; i++ ) {
        cout << pozitii_ans[i] - a.size() + 1 << " ";
    }
    return 0;
}