Cod sursa(job #1828883)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 13 decembrie 2016 23:39:52
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

template<typename T>
class Hash {
    public:
        Hash() :
            m_hashTable(kMod) {
        }

        void Add(T key) {
            for (T it : m_hashTable[key % kMod])
                if (it == key)
                    return;

            m_hashTable[key % kMod].push_back(key);
        }

        bool Find(T key) {
            for (T it : m_hashTable[key % kMod])
                if (it == key)
                    return true;

            return false;
        }

    private:
        std::vector< std::vector<T> > m_hashTable;
        static constexpr int kMod = 666013;
};

class Solver {
    public:
        Solver() {
        }

        void LoadTest(const std::string path) {
            std::ifstream inputFile(path);

            inputFile >> m_text;
            std::string word;
            while (inputFile >> word) {
                m_wordLen = (int)word.length();

                unsigned int val = 0;
                for (auto letter : word)
                    val = val*kBase + (letter - 'a');

                m_hashManager.Add(val);
            }

            inputFile.close();
        }

        void PrintSolution(const std::string path) {
            std::ofstream outputFile(path);
            outputFile << CountMatches() << '\n';
            outputFile.close();
        }

    private:
        int CountMatches() {
            unsigned int val = 0, power = 1;
            for (int i = 0; i < m_wordLen; ++i) {
                val = val*3 + (m_text[i] - 'a');
                power *= 3;
            }
            power /= 3;

            int res = 0;
            if (m_hashManager.Find(val))
                res++;

            for (int i = m_wordLen; i < (int)m_text.size(); ++i) {
                val -= (m_text[i - m_wordLen] - 'a')*power;
                val = 3*val + (m_text[i] - 'a');

                if (m_hashManager.Find(val))
                    res++;
            }

            return res;
        }

        int m_wordLen;
        std::string m_text;
        Hash<unsigned int> m_hashManager;

        static constexpr int kBase = 3;
};

int main() {
    Solver solver;
    solver.LoadTest("abc2.in");
    solver.PrintSolution("abc2.out");

    return 0;
}

//Trust me, I'm the Doctor!