Cod sursa(job #3233318)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 23:08:05
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.28 kb
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <fstream>
#include <cstring>

using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    TrieNode* fail;
    vector<int> output;

    TrieNode() : fail(nullptr) {}
};

class AhoCorasick {
public:
    AhoCorasick() {
        root = new TrieNode();
    }

    void insert(const string& word, int index) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->output.push_back(index);
    }

    void build() {
        queue<TrieNode*> q;
        root->fail = root;

        for (auto& pair : root->children) {
            pair.second->fail = root;
            q.push(pair.second);
        }

        while (!q.empty()) {
            TrieNode* current = q.front();
            q.pop();

            for (auto& pair : current->children) {
                char ch = pair.first;
                TrieNode* child = pair.second;
                TrieNode* fail = current->fail;

                while (fail != root && fail->children.find(ch) == fail->children.end()) {
                    fail = fail->fail;
                }

                if (fail->children.find(ch) != fail->children.end()) {
                    child->fail = fail->children[ch];
                } else {
                    child->fail = root;
                }

                child->output.insert(child->output.end(), child->fail->output.begin(), child->fail->output.end());
                q.push(child);
            }
        }
    }

    int search(const string& text, int wordCount) {
        TrieNode* node = root;
        vector<int> found(text.length(), 0);

        for (size_t i = 0; i < text.length(); ++i) {
            char ch = text[i];
            while (node != root && node->children.find(ch) == node->children.end()) {
                node = node->fail;
            }

            if (node->children.find(ch) != node->children.end()) {
                node = node->children[ch];
            } else {
                node = root;
            }

            for (int index : node->output) {
                found[i]++;
            }
        }

        int candidatePositions = 0;
        for (size_t i = 0; i <= text.length() - wordLength; ++i) {
            if (found[i] > 0) {
                candidatePositions++;
            }
        }

        return candidatePositions;
    }

    void setWordLength(int length) {
        wordLength = length;
    }

private:
    TrieNode* root;
    int wordLength;
};

int main() {
    ifstream infile("abc2.in");
    ofstream outfile("abc2.out");

    string text;
    infile >> text;

    AhoCorasick aho;
    int wordCount = 0;
    int wordLength = 0;

    string word;
    while (infile >> word) {
        aho.insert(word, wordCount++);
        wordLength = word.length();
    }

    aho.build();
    aho.setWordLength(wordLength);

    int result = aho.search(text, wordCount);
    outfile << result << endl;

    infile.close();
    outfile.close();

    return 0;
}