Cod sursa(job #2869880)

Utilizator beingsebiPopa Sebastian beingsebi Data 11 martie 2022 21:43:37
Problema Aho-Corasick Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.46 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
// #define f cin
// #define g cout
int rez[102], af[102];
struct aho
{
    aho *v[26], *exit, *par;
    int cnt, def;
    vector<int> leafs;
    char ch;
    string ss;
    aho()
    {
        for (int i = 0; i < 26; i++)
            v[i] = nullptr;
        exit = nullptr;
        par = nullptr;
        def = ch = cnt = 0;

        leafs.clear();
    }
} *rad = new aho;
struct box
{
    aho *x;
    box(aho *z)
    {
        x = z;
    }
};
vector<box> vec;
void adauga(const string &, const int);
string s;
void getexit();
// void dfs(box);
int32_t main()
{
    f >> s;
    int n;
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        static string ax;
        f >> ax;
        adauga(ax, i);
    }
    getexit();
    aho *ax = rad;
    for (const char &ch : s)
    {
        if (ax->v[ch - 'a'] != nullptr)
            ax = ax->v[ch - 'a'];
        else
        {
            while (ax != rad)
            {
                ax = ax->exit;
                if (ax->v[ch - 'a'] != nullptr)
                    break;
            }
            if (ax->v[ch - 'a'] != nullptr)
                ax = ax->v[ch - 'a'];
        }
        ax->cnt++;
    }
    reverse(vec.begin(), vec.end());
    for (const auto &i : vec)
    {
        aho *ac = i.x;
        for (const int &j : ac->leafs)
            af[j] = ac->cnt;
        ac->exit->cnt += ac->cnt;
    }
    // ax = rad;
    // dfs(box(ax));
    for (int i = 1; i <= n; i++)
        g << af[i] << '\n';
    // g << endl;
    // queue<box> q;
    // q.push(box(rad));
    // while (!q.empty())
    // {
    //     aho *ac = q.front().x;
    //     for (int i = 0; i < 26; i++)
    //         if (ac->v[i] != nullptr)
    //         {
    //             q.push(box(ac->v[i]));
    //             g << ac->v[i]->ss << "  " << ac->v[i]->par->ss << " " << ac->v[i]->exit->ss << " " << ac->v[i]->cnt << '\n';
    //         }
    //     q.pop();
    // }
    return 0;
}
// void dfs(box ax)
// {
//     aho *ac = ax.x;
//     for (int i = 0; i < 26; i++)
//         if (ac->v[i] != nullptr)
//         {
//             dfs(box(ac->v[i]));
//             // ac->cnt += ac->v[i]->cnt;
//         }

//     ac->exit->cnt += ac->cnt;
//     cout << ac->ss << " " << ac->cnt << '\n';
//     // ac->cnt += ac->def;
//     for (const auto i : ac->leafs)
//         af[i] += ac->cnt;
// }
void adauga(const string &s, const int ind)
{
    aho *ax = rad;
    for (const char &ch : s)
    {
        if (ax->v[ch - 'a'] == nullptr)
            ax->v[ch - 'a'] = new aho;
        ax->v[ch - 'a']->par = ax;
        ax = ax->v[ch - 'a'];
        ax->ss = ax->par->ss + ch;
        ax->ch = ch - 'a';
    }
    ax->leafs.push_back(ind);
}
void getexit()
{
    queue<box> q;
    q.push(box(rad));
    while (!q.empty())
    {
        aho *ac = q.front().x;
        vec.push_back(q.front());
        q.pop();
        if (ac == rad || ac->par == rad)
            ac->exit = rad;
        else
        {
            aho *j = ac->par->exit;
            while (j != rad && j->v[ac->ch] == nullptr)
                j = j->par->exit;
            if (j->v[ac->ch] != nullptr)
                j = j->v[ac->ch];
            ac->exit = j;
        }
        for (int i = 0; i < 26; i++)
            if (ac->v[i] != nullptr)
                q.push(box(ac->v[i]));
    }
}