Cod sursa(job #3233320)

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

using namespace std;

const int ALPHABET_SIZE = 3;

struct TrieNode {
    TrieNode* children[ALPHABET_SIZE];
    TrieNode* fail;
    bool is_end;

    TrieNode() : fail(nullptr), is_end(false) {
        memset(children, 0, sizeof(children));
    }
};

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

    ~AhoCorasick() {
        deleteTrie(root);
    }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->is_end = true;
    }

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

        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            if (root->children[i]) {
                root->children[i]->fail = root;
                q.push(root->children[i]);
            }
        }

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

            for (int i = 0; i < ALPHABET_SIZE; ++i) {
                if (current->children[i]) {
                    TrieNode* child = current->children[i];
                    TrieNode* fail = current->fail;

                    while (fail != root && !fail->children[i]) {
                        fail = fail->fail;
                    }

                    if (fail->children[i] && fail->children[i] != child) {
                        child->fail = fail->children[i];
                    } 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) {
            int idx = ch - 'a';
            while (node != root && !node->children[idx]) {
                node = node->fail;
            }

            if (node->children[idx]) {
                node = node->children[idx];
            } else {
                node = root;
            }

            if (node->is_end) {
                count++;
            }
        }

        return count;
    }

private:
    TrieNode* root;

    void deleteTrie(TrieNode* node) {
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            if (node->children[i]) {
                deleteTrie(node->children[i]);
            }
        }
        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;
}