Cod sursa(job #2806635)

Utilizator roberttrutaTruta Robert roberttruta Data 22 noiembrie 2021 21:00:39
Problema Aho-Corasick Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.6 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct nod
{
    int parinte;
    int last;
    int sufix;
    int aparitii;
    int copii[27];
};
vector <nod> trie;
char sir[1000005], cuvinte[105][10005];
int nr, poz_cuv[105];

void init(int index, int p)
{
    nr++;
    trie.push_back(nod());
    trie[index].parinte = p;
    trie[index].last = 26;
    trie[index].aparitii = 0;
    trie[index].sufix = -1;
    for(int i=0; i<26; i++)
        trie[index].copii[i] = 0;
}
void make_trie(char cuv[10005], int index)
{
    if(nr==0)
    {
        init(0,0);
    }
    int len = strlen(cuv);
    int poz = 0;
    int litera;
    for(int i=0; i<len; i++)
    {
        litera = cuv[i] - 'a';
        if(trie[poz].copii[litera] == 0)
        {
            trie[poz].copii[litera] = nr;
            init(nr,poz);
        }
        poz = trie[poz].copii[litera];
        trie[poz].last = litera;
    }
    poz_cuv[index] = poz;
}

void make_sufix(int poz)
{
    if(trie[poz].sufix == -1)
    {
        int litera = trie[poz].last;
        int p = trie[poz].parinte;
        if(p == 0)
        {
            trie[poz].sufix = 0;
        }
        else
        {
            do
            {
                if(trie[p].sufix == -1)
                    make_sufix(p);
                p = trie[p].sufix;
            }
            while(trie[p].copii[litera] == 0 && p != 0);
            trie[poz].sufix = trie[p].copii[litera];
            //daca nici in radacina nu este ultima litera atunci sufixul este chiar radacina
        }
    }
}

void nr_aparitii()
{
    int len = strlen(sir);
    int poz = 0;
    for (int i=0; i<len; i++)
    {
        int lit = sir[i] - 'a';
        while(trie[poz].copii[lit] == 0 && poz != -1)
        {
            poz = trie[poz].sufix;
        }
        if(poz != -1)
        {
            poz = trie[poz].copii[lit];
            trie[poz].aparitii++;
            int p = trie[poz].sufix;
            while(p != 0)
            {
                trie[p].aparitii++;
                p = trie[p].sufix;
            }
        }
        else
        {
            poz = 0;
        }
    }
}

int main()
{
    int i,n;
    f>>sir;
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>cuvinte[i];
        make_trie(cuvinte[i],i);
    }
    for(i=1; i<=n; i++)
    {
        make_sufix(poz_cuv[i]);
    }
    nr_aparitii();
    for(i=1; i<=n; i++)
    {
        g<<trie[poz_cuv[i]].aparitii<<'\n';
    }

    return 0;
}