Pagini recente » Cod sursa (job #1745953) | Cod sursa (job #2869187) | Cod sursa (job #1153858) | Cod sursa (job #1491035) | Cod sursa (job #2470317)
#include <fstream>
#include <vector>
#include <iostream>
#include <string>
#include <cstring>
#define MOD 6000
using namespace std;
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
char word[25];
char str[10000005];
int lgw;
vector < unsigned int > H[MOD];
int keyFinding()
{
int key = 0, lg = strlen(word); // might optimise in here
lgw = lg;
for(int i = 0; i < lg; i++)
key = key * 3 + (word[i] - 'a');
return key;
}
int Find(unsigned int x)
{
int key = x % MOD;
for(auto it : H[key])
if(it == x)
return 1;
return 0;
}
void Insert(int x)
{
int key = x % MOD;
int it = Find(x);
if (it == 0)
H[key].push_back(x);
}
int main()
{
unsigned int power = 1, result = 0;
fin >> str;
while(fin >> word)
Insert(keyFinding());
unsigned int HashValue = 0, lg = strlen(str);
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)
result += Find(HashValue);
}
fout << result << "\n";
return 0;
}