Cod sursa(job #2796331)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 7 noiembrie 2021 21:50:03
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>

using namespace std;

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

#define MOD (1 << 16)
#define BAZA 256
#define NMAX 1000

int pozitii_ans[NMAX];

int lg_put( int base, int power ) {
    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 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 ) {
    return ( code * BAZA + ch ) % MOD;
}

int remove_first_character( int code, char ch, int pow ) {
    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, i, ans;
    code_query = code_hash( query, pattern.size() - 1 );
    code_pattern = code_hash( pattern, pattern.size() );
    pow = lg_put( BAZA, pattern.size() - 1 );
    ans = 0;
    i = pattern.size() - 1;
    while ( i < query.size() ) {
        code_query = add_hash_character(code_query, query[i] );
        if ( code_pattern == code_query && check(query, pattern, i - pattern.size() + 1 ) ) {
            if ( ans < NMAX ) {
                pozitii_ans[ans++] = i;
            }
            else
                ans++;
        }
        code_query = remove_first_character( code_query, query[i - pattern.size() + 1], pow );
        i++;
    }
    return ans;
}

int 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;
}