Pagini recente » Cod sursa (job #65493) | Cod sursa (job #2810162) | Cod sursa (job #2796060) | Cod sursa (job #2319004) | Cod sursa (job #1705441)
#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 = 1 << 14;
vector <unsigned int> my_hash[MOD];
public:
bool find_hash( unsigned int hash_value ) {
int position = hash_value & (MOD - 1);
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 - 1);
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;
for( int i = 0; i < word_len; i ++ ) {
hash_value = ( hash_value << 2 ) + ( str[i] - 'a' );
if( i > 0 )
power = ( power + 2 ) & 31;
}
answer += my_hash.find_hash( hash_value );
for( int i = word_len; i < str_len; i ++ ) {
hash_value = (( hash_value - (( str[i - word_len] - 'a' ) << power ) + (1 << 30) ) << 2 ) + ( str[i] - 'a' );
answer += my_hash.find_hash( hash_value );
}
output_file << answer << "\n";
return 0;
}