Cod sursa(job #1498493)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 8 octombrie 2015 17:49:22
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
#include<string>
#include<vector>

using namespace std;

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

const int key = 1922923;
unsigned int p3[ 21 ];
vector< unsigned int > h[ key ];
string s, cuv;

bool hash_search( unsigned int x ) {
    unsigned int k = x % key;
    for( int i = 0; i < ( int )h[ k ].size(); ++ i ) {
        if ( h[ k ][ i ] == x ) {
            return 1;
        }
    }
    return 0;
}
void precalc() {
    p3[ 0 ] = 1;
    for( int i = 1; i < 20; ++ i ) {
        p3[ i ] = p3[ i - 1 ] * 3;
    }
}
int main() {
    int l;
    fin >> s;
    precalc();
    while ( fin >> cuv ) {
        unsigned int x = 0;
        for( int i = 0; i < ( int )cuv.size(); ++ i ) {
            x = (x * 3 + cuv[ i ] - 'a');
        }
        if ( hash_search( x ) == 0 ) {
            h[ x % key ].push_back( x );
        }
        l = ( int )cuv.size();
    }

    int ans = 0;
    long long x = 0;
    for( int i = 0; i < ( int )s.size(); ++ i ) {
        x = (x * 3 + s[ i ] - 'a');
        if ( i >= l - 1 ) {
            ans += hash_search( x );
            x -= (p3[ l - 1 ] * (s[ i - l + 1 ] - 'a') );
        }
    }
    fout << ans << "\n";
    fin.close();
    fout.close();
    return 0;
}