Pagini recente » Cod sursa (job #546218) | Cod sursa (job #1720379) | Monitorul de evaluare | Cod sursa (job #1356125) | Cod sursa (job #1081100)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
const char infile[] = "abc2.in";
const char outfile[] = "abc2.out";
ifstream fin(infile);
ofstream fout(outfile);
const int BASE = 3;
const int oo = 0x3f3f3f3f;
const int MOD = 1613;
typedef unsigned long long uint;
typedef vector<int> :: iterator It;
const inline int min(const int &a, const int &b) { if( a > b ) return b; return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b; return a; }
const inline void Get_min(int &a, const int b) { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b) { if( a < b ) a = b; }
template <class T>
class Hash {
private:
vector <T> _hash[MOD];
inline int key(const int &value) {
return value % MOD;
}
public:
inline void add(const T &value) {
_hash[key(value)].push_back(value);
}
inline bool find(const T &value) {
int keyy = key(value);
for(typename vector < T> :: iterator it = _hash[keyy].begin(), fin = _hash[keyy].end(); it != fin ; ++ it)
if(*it == value)
return true;
return false;
}
};
inline uint getInt(const char &c) {
return c - 'a';
}
string Text, s;
uint sigma;
inline int getValue(const string &p) {
uint value = 0;
uint i = 0;
for(i = 0, sigma = p.size() ; i < sigma ; ++ i)
value = value * BASE + getInt(p[i]);
return value;
}
Hash <uint> _hash;
int main() {
fin >> Text;
while(fin >> s)
_hash.add(getValue(s));
uint value = 0;
uint _base = 1;
for(uint i = 0 ; i < sigma ; ++ i) {
value = value * BASE + getInt(Text[i]);
_base = _base * BASE;
}
uint Ans = 0;
Ans += _hash.find(value);
for(uint i = sigma , sz = Text.size() ; i < sz ; ++ i) {
value = value * BASE + getInt(Text[i]);
value = value - _base * getInt(Text[i - sigma]);
Ans += _hash.find(value);
}
fout << Ans << '\n';
fin.close();
fout.close();
return 0;
}