Cod sursa(job #2961570)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 6 ianuarie 2023 18:29:44
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.67 kb
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

ifstream in ("ahocorasick.in");
ofstream out ("ahocorasick.out");

const int sigma = 26, max_size = 1e2 + 1;

struct str{
    int ct;
    str * fii[sigma], * fail;
    vector <int> cuv;
    str()
    {
        ct = 0;
        for (int i = 0; i < sigma; i++)
        {
            fii[i] = 0;
        }
        fail = 0;
    }
};

str * t = new str;
int ans[max_size], sz;
vector <str *> v;
string s, cuvinte[max_size];

void ins (str * nod, int poz, int index)
{
    if (poz == sz)
    {
        nod -> cuv.push_back(index);
        return;
    }
    int urm = cuvinte[index][poz] - 'a';
    if (nod -> fii[urm] == 0)
    {
        nod -> fii[urm] = new str;
    }
    ins(nod -> fii[urm], poz + 1, index);
}

void bfs ()
{
    queue <str *> q;
    q.push(t);
    while (!q.empty())
    {
        str * nod = q.front();
        q.pop();
        v.push_back(nod);
        for (int i = 0; i < sigma; i++)
        {
            if (nod -> fii[i] == 0)
                continue;
            str * fail = nod -> fail, * urm = nod -> fii[i];
            q.push(urm);
            if (nod == t)
            {
                urm -> fail = nod;
                continue;
            }
            while (fail != t && fail -> fii[i] == 0)
            {
                fail = fail -> fail;
            }
            if (fail -> fii[i] != 0)
            {
                urm -> fail = fail -> fii[i];
            }
            else
            {
                urm -> fail = t;
            }
        }
    }
}

void antibfs ()
{
    reverse(v.begin(), v.end());
    for (vector <str *> :: iterator it = v.begin(); it != v.end(); it++)
    {
        str * nod = * it;
        if (nod == t)
            continue;
        nod -> fail -> ct += nod -> ct;
        for (auto f : nod -> cuv)
        {
            ans[f] = nod -> ct;
        }
    }
}

int main ()
{
    in >> s;
    int n;
    in >> n;
    for (int i = 0; i < n; i++)
    {
        in >> cuvinte[i];
        sz = cuvinte[i].size();
        ins(t, 0, i);
    }
    bfs();
    sz = s.size();
    str * nod = t;
    for (int i = 0; i < sz; i++)
    {
        int urm = s[i] - 'a';
        while (nod != t && nod -> fii[urm] == 0)
        {
            nod = nod -> fail;
        }
        if (nod -> fii[urm] != 0)
        {
            nod = nod -> fii[urm];
        }
        nod -> ct++;
    }
    antibfs();
    for (int i = 0; i < n; i++)
    {
        out << ans[i] << '\n';
    }
    in.close();
    out.close();
    return 0;
}