Cod sursa(job #3307379)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 20 august 2025 15:38:39
Problema Aho-Corasick Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.96 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

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

/* 
    mici modificari ca sa verific daca e codul mai rapid
*/

const int NMAX = 1e6 + 5;

struct Node {
    int kids[26];   
    int suffixLink;
    int cnt;

    void init() {
	for (int i = 0; i < /*alphaSize*/26; i++) {
            kids[i] = -1;
        }
        suffixLink = -1;
        cnt = 0;
    }
} nodes[NMAX];

int q[NMAX], qsize;

class AhoCorasick {
public:

    int root;
    int alphaSize;
    int nrNodes;

    AhoCorasick(int size) {
        nrNodes = 0;
        alphaSize = size;
        root = ++nrNodes;
        nodes[root].init();
    }

    int insert(string s) {
        int node = root;

        for (char ch: s) {
            int childId = int(ch - 'a');
            if (nodes[node].kids[childId] == -1) {
                nodes[node].kids[childId] = ++nrNodes;
                nodes[nrNodes].init();
            }

            node = nodes[node].kids[childId];
        }

        return node;
    }

    void solvePrefix(int node, int childId) {
        int pref = nodes[node].suffixLink;

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

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

    void buildAndSolve(string s) {
        nodes[root].suffixLink = root;

        q[qsize++] = root;

        for (int j = 0; j < qsize; j++) {
            int node = q[j];

            for (int i = 0; i < alphaSize; i++) {
                if (nodes[node].kids[i] != -1) {
                    solvePrefix(node, i);
                    q[qsize++] = nodes[node].kids[i];
                }
            }
        }

        int node = root;

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

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

            if (nodes[node].kids[childId] != -1) {
                node = nodes[node].kids[childId];
            }

            nodes[node].cnt++;
        }

        for (int i = qsize - 1; i >= 0; i--) {
            nodes[nodes[q[i]].suffixLink].cnt += nodes[q[i]].cnt;
        }
    }
};

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

    AhoCorasick automaton(26);

    int termNodes[n];
    for (int i = 0; i < n; i++) {
        string pattern;
        cin >> pattern;

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

    automaton.buildAndSolve(text);

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