Cod sursa(job #1705447)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 20 mai 2016 16:57:50
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <bits/stdc++.h>

const int DIM = 1e7;
const int EXP = 2e2;
using namespace std;

char str[DIM], word[EXP]; unsigned int hash_value, power;
int str_len, word_len, answer;

class nrx_hash {
    private:
        static const int MOD = 90907;
        vector <unsigned int> my_hash[MOD];
    public:
        bool find_hash( unsigned int hash_value ) {
            int position = hash_value % MOD;

            vector <unsigned int> :: iterator it;
            for( it = my_hash[position].begin(); it != my_hash[position].end(); it ++ ) {
                unsigned int current_hash = *it;

                if( current_hash == hash_value )
                    return true;
            }

            return false;
        }

        void insert_hash( unsigned int hash_value ) {
            int position = hash_value % MOD;

            vector <unsigned int> :: iterator it;
            for( it = my_hash[position].begin(); it != my_hash[position].end(); it ++ ) {
                unsigned int current_hash = *it;

                if( current_hash == hash_value )
                    return;
            }

            my_hash[position].push_back( hash_value );
            return;
        }
} my_hash;

int main() {

    ifstream input_file ( "abc2.in"  );
    ofstream output_file( "abc2.out" );

    input_file >> str; str_len = strlen( str );

    while( true ) {
        memset( word, 0, sizeof(word) );
        input_file >> word;

        if( word[0] == 0 )
            break;

        word_len = strlen( word );
        hash_value = 0;

        for( int i = 0; i < word_len; i ++ )
            hash_value = ( hash_value << 2 ) + ( word[i] - 'a' );

        if( !my_hash.find_hash( hash_value ) )
            my_hash.insert_hash( hash_value );
    }

    hash_value = 0; power = 1;
    for( int i = 0; i < word_len; i ++ ) {
        hash_value = ( hash_value << 2 ) + ( str[i] - 'a' );

        if( i > 0 )
            power <<= 2;
    }

    answer += my_hash.find_hash( hash_value );

    for( int i = word_len; i < str_len; i ++ ) {
        hash_value = (( hash_value - ( power * ( str[i - word_len] - 'a' ) ) ) << 2 ) + ( str[i] - 'a' );
        answer += my_hash.find_hash( hash_value );
    }

    output_file << answer << "\n";
    return 0;
}