Pagini recente » Statistici Rusu Alex (TheStifmeister) | Monitorul de evaluare | Istoria paginii runda/dinamica_test/clasament | Istoria paginii runda/vendetta_dc4/clasament | Cod sursa (job #1462891)
#include <vector>
#include <algorithm>
#include <string>
#include <fstream>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int NMAX = 50000;
const int MOD = 666013;
struct DAP {
int v,c;
};
string s;
string c;
vector <int> H[MOD+1];
int L;
int Ans = 0;
int FORMULA( string str ) {
int p = 1, k = 0;
for( int i = (int)str.size()-1; i >= 0; --i, p*= 3 ) {
k += p * (int)( str[i] - 'a' );
}
return k;
}
void Push_hash( int val ) {
int key = val % MOD;
H[key].push_back( val );
}
void Check_hash( int val ) {
int key = val % MOD;
for( int i = 0; i < (int)H[key].size(); ++i ) {
if( H[key][i] == val ) {
++Ans;
break;
}
}
}
int main() {
in >> s;
while( in >> c ) {
L = (int)c.size();
int aux = FORMULA(c);
Push_hash( aux );
}
long long k = 0, p = 1;
for( int i = L-1; i >= 0; --i ) {
k += p * (int)( s[i] - 'a' );
p *= 3;
}
Check_hash( k );
p /= 3;
for( int i = L; i < (int)s.size(); ++i ) {
k -= (int)( s[i-L] - 'a' ) * p;
k = k*3 + (int)( s[i] - 'a' );
Check_hash( k );
}
out << Ans << '\n';
return 0;
}