Cod sursa(job #2899797)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 9 mai 2022 08:28:11
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
#include <bits/stdc++.h>
#define car(x) (x-'a')
#define Nmax 1000005
#define Pmax 1005

using namespace std;

ifstream fin("ahocorasik.in");
ofstream fout("ahocorasik.out");

int n, nr_cuv, ap[Pmax];
char c[Nmax], p[Pmax];

struct trie
{
    trie *fii[26], *suffix_link, *output_link;
    int ind;

    trie()
    {
        for(int i=0;i<26;i++)
            fii[i]=nullptr;
        suffix_link=nullptr;
        output_link=nullptr;
        ind=0;
    }
};
trie *root = new trie();

void ins(trie *root, char p[], int index)
{
    int n=strlen(p);
    trie *nod = root;

    for(int i=0;i<n;i++)
    {
        if(nod->fii[car(p[i])]==nullptr)
            nod->fii[car(p[i])] = new trie();
        nod = nod->fii[car(p[i])];
    }
    nod->ind = index;
}

void bfs(trie *root)
{
    queue <trie*> q;

    for(int i=0;i<26;i++)
        if(root->fii[i]!=nullptr)
        {
            q.push(root->fii[i]);
            root->fii[i]->suffix_link=root;
        }

    while(!q.empty())
    {
        trie *u = q.front();
        q.pop();
        for(int i=0;i<26;i++)
            if(u->fii[i]!=nullptr)
            {
                trie *suffix = u->suffix_link;

                while(suffix->fii[i]==nullptr && suffix!=root)
                    suffix = suffix->suffix_link;

                if(suffix->fii[i]!=nullptr)
                    u->fii[i]->suffix_link = suffix->fii[i];
                else u->fii[i]->suffix_link = root;

                q.push(u->fii[i]);
            }

        if(u->suffix_link->ind > 0)
            u->output_link = u->suffix_link;
        else u->output_link = u->suffix_link->output_link;
    }
}

void ahoaho(trie *root, char c[])
{
    int n=strlen(c);
    trie *nod = root;
    for(int i=0;i<n;i++)
        if(nod->fii[car(c[i])]!=nullptr)
        {
            nod = nod->fii[car(c[i])];
            if(nod->ind>0)
                ap[nod->ind]++;

            trie *aux = nod->output_link;
            while(aux!=nullptr)
            {
                ap[aux->ind]++;
                aux=aux->output_link;
            }
        }
        else
        {
            while(nod != root && nod->fii[car(c[i])]==nullptr)
                nod=nod->suffix_link;

            if(nod->fii[car(c[i])])
                i--;
        }
}

int main()
{
    fin >> c;
    fin >> nr_cuv;
    for(int i=1;i<=nr_cuv;i++)
    {
        fin >> p;
        ins(root, p, i);
    }

    bfs(root);

    ahoaho(root, c);

    for(int i=1;i<=nr_cuv;i++)
        fout << ap[i] << '\n';
    return 0;
}