Pagini recente » Cod sursa (job #1751334) | Cod sursa (job #198199) | Cod sursa (job #2573128) | Cod sursa (job #2942864) | Cod sursa (job #1498493)
#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;
}