Cod sursa(job #2286051)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 19 noiembrie 2018 19:15:57
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.02 kb
#include <bits/stdc++.h>
  
#if 1
    #define pv(x) std::cerr<<#x<<" = "<<(x)<<"; ";std::cerr.flush()
    #define pn std::cerr<<std::endl
#else
    #define pv(x)
    #define pn
#endif
  
// #if 1
#ifdef INFOARENA
    std::ifstream in("ahocorasick.in");
    std::ofstream out("ahocorasick.out");
#else
    #define in cin
    #define out cout
#endif

class ahoCorasick {
    private:
    static const char minChar = 'a', maxChar = 'z';
    static const int alphabetSize = maxChar - minChar + 1;
    std::vector<std::string> dictionary;
    int dictionarySize = 0;

    struct trieNode {
        int num = 0, length = 0;
        std::vector<int> wordIndex;
        trieNode* blue = this;
        trieNode* nxt[alphabetSize] = {};
    } *root;
    
    std::vector<trieNode*> Q;
    bool resetNeeded = false;

    public:
    ahoCorasick(std::vector<std::string> _dictionary, bool saveDict = false) {
        if (saveDict) {
            dictionary = _dictionary;
        }
        dictionarySize = _dictionary.size();

        root = new trieNode;
        for (int i = 0; i < (int)_dictionary.size(); ++i) {
            add(root, _dictionary[i], 0, i);
        }
        built(root);
    }

    std::vector<std::string> getDictionary() {
        return dictionary;
    }

    void getNumberOfOccurences(const std::string& text, std::vector<int>& occ) {
        occ.assign(dictionarySize, 0);

        if (resetNeeded) {
            reset();
        }
        resetNeeded = true;

        trieNode* node = root;
        for (int tdx = 0; tdx < (int)text.size(); ++tdx) {
            char c = text[tdx];
            int let = c - minChar;

            while (node->nxt[let] == nullptr) {
                node = node->blue;
            }
            node = node->nxt[let];

            node->num += 1;
        }

        for (int qdx = Q.size() - 1; qdx >= 0; --qdx) {
            trieNode* node = Q[qdx];
            for (int wdx : node->wordIndex) {
                occ[wdx] += node->num;
            }
            node->blue->num += node->num;
        }
    }

    private:
    void add(trieNode* node, const std::string& word, int idx, int wdx) {
        node->length = idx;
        if (idx == (int)word.size()) {
            node->wordIndex.push_back(wdx);
            return;
        }

        int let = word[idx] - minChar;
        if (node->nxt[let] == nullptr) {
            node->nxt[let] = new trieNode;
        }
        add(node->nxt[let], word, idx + 1, wdx);
    }

    void built(trieNode* root) {
        for (int let = 0; let < alphabetSize; ++let) {
            if (root->nxt[let] == nullptr) {
                root->nxt[let] = root;
            }
            else {
                trieNode* follow = root->nxt[let];
                follow->blue = root;
                Q.push_back(follow);
            }
        }

        int qdx = 0;
        while (qdx < (int)Q.size()) {
            trieNode *node = Q[qdx++];

            for (char c = minChar; c <= maxChar; ++c) {
                int let = c - minChar;
                trieNode* follow = node->nxt[let];
                if (follow == nullptr) {
                    continue;
                }

                trieNode* aux = node->blue;
                while (aux->nxt[let] == nullptr) {
                    aux = aux->blue;
                }
                aux = aux->nxt[let];

                follow->blue = (aux == follow) ? root : aux; ////
                Q.push_back(follow);
            }
        }
    }

    void reset() {
        for (int let = 0; let < alphabetSize; ++let) {
            if (root->nxt[let] != root) {
                dfsReset(root->nxt[let]);
            }
        }
        root->num = 0;
    }

    void dfsReset(trieNode* node) {
        node->num = 0;
        for (int let = 0; let < alphabetSize; ++let) {
            if (node->nxt[let] != nullptr) {
                dfsReset(node->nxt[let]);
            }
        }
    }

    void dfsDestruct(trieNode* node) {
        for (int let = 0; let < alphabetSize; ++let) {
            if (node->nxt[let] != nullptr) {
                dfsDestruct(node->nxt[let]);
            }
        }
        delete node;
    }

    public:
    ~ahoCorasick() {
        for (int let = 0; let < alphabetSize; ++let) {
            if (root->nxt[let] != root) {
                dfsDestruct(root->nxt[let]);
            }
        }
        delete root;
    }
};


using namespace std;
 
int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
 
    string text;
    in >> text;
    int N;
    in >> N;
    vector<string> dict(N);
    for (string& word : dict) {
        in >> word;
    }

    ahoCorasick ac(dict);
    vector<int> occ;
    ac.getNumberOfOccurences(text + text + "sadasdaaaaaaabbbbbbbbbaaaaaaabsadasdaaweqrdtgfdg" + text, occ); // test daca reset functioneaza;
    ac.getNumberOfOccurences(text, occ);
    for (int o : occ) {
        out << o << '\n';
    }
 
    return 0;
}