Pagini recente » Cod sursa (job #1835267) | Cod sursa (job #1375606) | Cod sursa (job #1204665) | Cod sursa (job #573533) | Cod sursa (job #2474131)
#include <bits/stdc++.h>
#define llg long long
std::ifstream input ("abc2.in");
std::ofstream output("abc2.out");
int len;
int cod[256];
std::string str;
std::map <llg, int> map;
std::set <llg> set;
llg hashFunc(std::string word) {
llg hash = 0;
for (int i=0; i<len; ++i)
hash = hash*3LL + 1LL*cod[word[len-i-1]];
if (set.find(hash) != set.end()) return -1;
set.insert(hash);
return hash;
}
int main()
{
cod['a'] = 0, cod['b'] = 1, cod['c'] = 2;
input >> str;
std::string word;
input >> word;
len = word.size();
if (len > str.size()) {
output << 0;
return 0;
}
llg hash = 0;
llg p = 1;
for (int i=0; i<len; ++i) {
hash = hash*3LL + 1LL*cod[str[str.size()-i-1]];
p *= 3LL;
} ++ map[hash];
p /= 3LL;
for (int i = str.size()-len-1; i>=0; --i) {
hash = hash - 1LL*cod[str[i+len]]*p;
hash = hash*3LL + 1LL*cod[str[i]];
++ map[hash];
}
llg ans = 0;
ans += 1LL*map[hashFunc(word)];
while (input >> word)
ans += 1LL*map[hashFunc(word)];
output << ans;
return 0;
}