Cod sursa(job #2474131)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 14 octombrie 2019 19:11:38
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#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;
}