Cod sursa(job #3307334)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 20 august 2025 12:12:33
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.22 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");

class Node {
public:

    vector<Node*> kids;
    Node* suffixLink;
    int cnt;

    Node(int alphaSize) {
        kids.resize(alphaSize, NULL);
        suffixLink = NULL;
        cnt = 0;
    }
};

class AhoCorasick {
public:

    Node* root;
    int alphaSize;

    AhoCorasick(int size) {
        alphaSize = size;
        root = new Node(size);
    }

    bool checkChild(Node* node, int childId) {
        return (node->kids[childId] != NULL);
    }

    void addChild(Node* node, int childId) {
        node->kids[childId] = new Node(alphaSize);
    }

    Node* insert(string s) {
        Node* node = root;

        for (char ch: s) {
            int childId = int(ch - 'a');
            if (!checkChild(node, childId)) {
                addChild(node, childId);
            }

            node = node->kids[childId];
        }

        return node;
    }

    void solvePrefix(Node* node, int childId) {
        Node* pref = node->suffixLink;

        while (pref != root && !pref->kids[childId]) {
            pref = pref->suffixLink;
        }

        if(pref->kids[childId] && pref->kids[childId] != node->kids[childId]) {
            node->kids[childId]->suffixLink = pref->kids[childId];
        } else {
            node->kids[childId]->suffixLink = root;
        }
    }

    void build() {
        root->suffixLink = root;

        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node* node = q.front();
            q.pop();

            for (int i = 0; i < alphaSize; i++) {
                if (node->kids[i]) {
                    solvePrefix(node, i);
                    q.push(node->kids[i]);
                }
            }
        }
    }

    void solve(string s) {
        Node* node = root;

        for (char ch: s) {
            int childId = int(ch - 'a');

            while(node != root && !node->kids[childId]) {
                node = node->suffixLink;
            }

            if (node->kids[childId]) {
                node = node->kids[childId];
            }

            node->cnt++;
        }

        vector<Node*> bfsOrder;
        bfsOrder.push_back(root);

        for (int i = 0; i < int(bfsOrder.size()); i++) {
            Node* node = bfsOrder[i];

            for (int j = 0; j < alphaSize; j++) {
                if (node->kids[j]) {
                    bfsOrder.push_back(node->kids[j]);
                }
            }
        }

        for (int i = bfsOrder.size() - 1; i >= 0; i--) {
            Node* node = bfsOrder[i];
            node->suffixLink->cnt += node->cnt;
        }
    }
};

int main() {
    int n;
    string text;
    cin >> text >> n;

    AhoCorasick automaton(26);

    vector <Node*> termNodes(n, NULL);
    for (int i = 0; i < n; i++) {
        string pattern;
        cin >> pattern;

        termNodes[i] = automaton.insert(pattern);
    }

    automaton.build();
    automaton.solve(text);

    for (int i = 0; i < n; i++) {
        cout << termNodes[i]->cnt << '\n';
    }
}