Cod sursa(job #3303170)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 14 iulie 2025 14:07:02
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int NMAX = 100, SIGMA = 26;
int n, ans[NMAX];

struct TrieNode
{
    int ending = 0;
    TrieNode *children[SIGMA], *fail_link;
    vector<int> output;
    TrieNode()
    {
        fill(children, children + SIGMA, nullptr);
        fail_link = nullptr;
    }
};
TrieNode *root = new TrieNode;
vector<TrieNode*> BFS_order;

void adauga(const string &pattern, int idx)
{
    TrieNode *node = root;
    for(char ch : pattern)
    {
        if(node->children[ch - 'a'] == nullptr)
            node->children[ch - 'a'] = new TrieNode;
        node = node->children[ch - 'a'];
    }
    node->output.push_back(idx);
}

void build_fail_links()
{
    queue<TrieNode*> q;
    root->fail_link = root;
    q.push(root);
    while(!q.empty())
    {
        TrieNode *node = q.front();
        q.pop();
        BFS_order.push_back(node);
        for(char ch = 'a'; ch <= 'z'; ch++)
        {
            TrieNode *child = node->children[ch - 'a'];
            if(child == nullptr)
                continue;
            TrieNode *fall_back = node->fail_link;
            while(fall_back != root && fall_back->children[ch - 'a'] == nullptr)
                fall_back = fall_back->fail_link;
            child->fail_link = (fall_back->children[ch - 'a'] != nullptr && fall_back->children[ch - 'a'] != child ? fall_back->children[ch - 'a'] : root);
            q.push(child);
        }
    }
}

void cauta(const string &text)
{
    TrieNode *node = root;
    for(char ch : text)
    {
        while(node != root && node->children[ch - 'a'] == nullptr)
            node = node->fail_link;
        if(node->children[ch - 'a'] != nullptr)
            node = node->children[ch - 'a'];
        node->ending++;
    }
    reverse(BFS_order.begin(), BFS_order.end());
    for(auto node : BFS_order)
    {
        for(int idx : node->output)
            ans[idx] = node->ending;
        if(node->fail_link != nullptr)
            node->fail_link->ending += node->ending;
    }
}

int main()
{
    string text;
    fin >> text >> n;
    for(int i = 0; i < n; i++)
    {
        string pattern;
        fin >> pattern;
        adauga(pattern, i);
    }
    build_fail_links();
    cauta(text);
    for(int i = 0; i < n; i++)
        fout << ans[i] << "\n";

    fin.close();
    fout.close();
    return 0;
}