Pagini recente » Cod sursa (job #3212092) | Cod sursa (job #2870222) | Cod sursa (job #2532163) | Cod sursa (job #1127691) | Cod sursa (job #1705443)
#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;
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 ) ) << 2 ) + ( str[i] - 'a' );
answer += my_hash.find_hash( hash_value );
}
output_file << answer << "\n";
return 0;
}