Pagini recente » Cod sursa (job #241605) | Cod sursa (job #3003431) | Cod sursa (job #2207983) | Cod sursa (job #2635823) | Cod sursa (job #3278099)
#include <bits/stdc++.h>
std::ifstream fin("abc2.in");
std::ofstream fout("abc2.out");
const int SIZE = 20;
const int64_t base = 269696969;
int word_len;
std::string text, word;
int64_t power[SIZE + 1];
std::unordered_map<uint64_t, bool> hash_words;
void precompute_powers()
{
power[0] = 1;
for(int i = 1; i <= SIZE; ++i)
power[i] = power[i - 1] * base;
}
int main()
{
std::ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fin >> text;
precompute_powers();
while(!fin.eof())
{
fin >> word;
word_len = word.length();
uint64_t pattern_hash = 0;
for(int i = 0; i < word_len; ++i)
pattern_hash = pattern_hash * base + (word[i] - 'a' + 1);
hash_words[pattern_hash] = true;
}
if(text.length() < word_len)
{
fout << 0;
return 0;
}
uint64_t text_hash = 0;
for(int i = 0; i < word_len; ++i)
text_hash = text_hash * base + (text[i] - 'a' + 1);
int count = 0;
if(hash_words.find(text_hash) != hash_words.end())
count++;
for(int i = word_len; i < text.length(); ++i)
{
text_hash = (text_hash - ((text[i - word_len] - 'a' + 1) * power[word_len - 1])) * base + (text[i] - 'a' + 1);
if(hash_words.find(text_hash) != hash_words.end())
count++;
}
fout << count;
return 0;
}