Pagini recente » Cod sursa (job #1337336) | Cod sursa (job #2375825) | Cod sursa (job #2180609) | Cod sursa (job #1307149) | Cod sursa (job #2470299)
#include <fstream>
#include <vector>
#include <iostream>
#include <string>
#define MOD 6660
using namespace std;
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
string str, word;
int lgw;
vector < unsigned int > H[MOD];
int keyFinding(string Word)
{
int key = 0, lg = Word.size(); // might optimise in here
lgw = lg;
for(int i = 0; i < lg; i++)
key = key * 3 + (Word[i] - 'a');
return key;
}
vector < unsigned int > :: iterator Find(int x)
{
int key = x % MOD;
vector < unsigned int > :: iterator it;
for(it = H[key].begin(); it != H[key].end(); ++it)
if(*it == x)
return it;
return H[key].end();
}
bool FindFinal(int x)
{
int key = x % MOD;
vector < unsigned int > :: iterator it;
for(it = H[key].begin(); it != H[key].end(); ++it)
if(*it == x)
return true;
return false;
}
void Insert(int x)
{
int key = x % MOD;
vector < unsigned int > :: iterator it = Find(x);
if (it != H[key].end())
return;
H[key].push_back(x);
}
int main()
{
int power = 1, result = 0;
fin >> str;
while(fin >> word)
Insert(keyFinding(word));
int HashValue = 0, lg = str.size();
for(int i = 1; i <= lgw; i++)
power *= 3;
for(int i = 0; i < lg; i++)
{
HashValue = HashValue * 3 + (str[i] - 'a');
if(i >= lgw)
HashValue = HashValue - power * (str[i - lgw] - 'a');
if(i >= lgw - 1)
if(FindFinal(HashValue))
result++;
}
fout << result << "\n";
return 0;
}