Cod sursa(job #3233322)

Utilizator MirceaDonciuLicentaLicenta Mircea Donciu MirceaDonciuLicenta Data 2 iunie 2024 23:17:39
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 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;
    bool is_end;

    TrieNode() : fail(nullptr), is_end(false) {}
};

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

    ~AhoCorasick() {
        deleteTrie(root);
    }

    void insert(const string& word) {
        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->is_end = true;
    }

    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->is_end = child->is_end || child->fail->is_end;
                q.push(child);
            }
        }
    }

    int search(const string& text) {
        TrieNode* node = root;
        int count = 0;

        for (char ch : text) {
            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;
            }

            TrieNode* temp = node;
            while (temp != root) {
                if (temp->is_end) {
                    count++;
                }
                temp = temp->fail;
            }
        }

        return count;
    }

private:
    TrieNode* root;

    void deleteTrie(TrieNode* node) {
        for (auto& pair : node->children) {
            deleteTrie(pair.second);
        }
        delete node;
    }
};

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

    string text;
    infile >> text;

    AhoCorasick aho;
    string word;
    while (infile >> word) {
        aho.insert(word);
    }

    aho.build();

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

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

    return 0;
}