Cod sursa(job #3303165)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 14 iulie 2025 13:46:56
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.44 kb
#pragma GCC optimize("O3")
#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
{
    TrieNode *children[SIGMA], *fail_link;
    vector<int> output;
    TrieNode()
    {
        fill(children, children + SIGMA, nullptr);
        fail_link = nullptr;
    }
};
TrieNode *root = new TrieNode;

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;
    for(char ch = 'a'; ch <= 'z'; ch++)
    {
        if(root->children[ch - 'a'] != nullptr)
        {
            root->children[ch - 'a']->fail_link = root;
            q.push(root->children[ch - 'a']);
        }
    }
    while(!q.empty())
    {
        TrieNode *node = q.front();
        q.pop();
        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 != nullptr && fall_back->children[ch - 'a'] == nullptr)
                fall_back = fall_back->fail_link;
            child->fail_link = (fall_back != nullptr ? fall_back->children[ch - 'a'] : root);
            child->output.insert(child->output.end(), child->fail_link->output.begin(), child->fail_link->output.end());
            q.push(child);
        }
    }
}

void cauta(const string &text)
{
    TrieNode *node = root;
    for(char ch : text)
    {
        while(node != nullptr && node->children[ch - 'a'] == nullptr)
            node = node->fail_link;
        node = (node != nullptr ? node->children[ch - 'a'] : root);
        for(int idx : node->output)
            ans[idx]++;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);

    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;
}