Pagini recente » Cod sursa (job #2155355) | Cod sursa (job #1733184) | Cod sursa (job #2733178) | Cod sursa (job #2336620) | Cod sursa (job #2261189)
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 1e7 + 10;
const int MMAX = 5e4 + 10;
const int Base = 3;
const int MOD = 123457;
char Text[NMAX], Word[MMAX];
vector <int> Hash[MOD];
inline void insertHash(const long long &x)
{
Hash[x % MOD].push_back(x);
}
bool findHash(const long long &x)
{
int key = x % MOD;
for (auto i : Hash[key])
if (i == x)
return true;
return false;
}
int main()
{
ifstream fin("abc2.in");
ofstream fout("abc2.out");
int WordSize, TextSize;
fin >> (Text + 1);
TextSize = strlen(Text + 1);
unsigned int hashCode;
while (fin >> (Word + 1))
{
WordSize = strlen(Word + 1);
hashCode = 0;
for (int i = 1;i <= WordSize;++i)
hashCode = hashCode * Base + (Word[i] - 'a');
insertHash(hashCode);
}
unsigned int p = 1;
for (int i = 1;i < WordSize;++i)
p *= Base;
hashCode = 0;
for (int i = 1;i <= WordSize;++i)
hashCode = hashCode * Base + (Text[i] - 'a');
int answer = findHash(hashCode);
for (int i = WordSize + 1;i <= TextSize;++i)
{
hashCode -= (Text[i - WordSize] - 'a') * p;
hashCode = hashCode * Base + (Text[i] - 'a');
if (findHash(hashCode))
++answer;
}
fout << answer << "\n";
fin.close();
fout.close();
return 0;
}