Cod sursa(job #2900052)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 9 mai 2022 23:41:54
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <bits/stdc++.h>
#define car(x) (x-'a')
#define Nmax 1000005
#define Pmax 10005

using namespace std;

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

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

struct trie
{
    trie *fii[26], *suffix_link;
    vector<int> ind;
    int cnt;

    trie()
    {
        for(int i=0;i<26;i++)
            fii[i]=nullptr;
        suffix_link=nullptr;
        cnt=0;
    }
};

trie *root = new trie();
stack <trie*> invbfs;

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.push_back(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();
        invbfs.push(u);
        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]);
            }
    }
}

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

        nod->cnt++;
    }

}

void antibfs()
{
    while(!invbfs.empty())
    {
        trie *u = invbfs.top();
        invbfs.pop();
        if(u->suffix_link!=nullptr) u->suffix_link->cnt += u->cnt;

        for(auto it:u->ind)
            ap[it]+=u->cnt;
    }
}


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);
    antibfs();

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