Cod sursa(job #2900532)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 11 mai 2022 08:22:08
Problema Aho-Corasick Scor 100
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
{
    int suffix_link, cnt, fii[26];
    vector <int> ind;
    trie()
    {
        suffix_link=-1;
        cnt=0;
        for(int i=0;i<26;i++)
            fii[i]=-1;
    }
};

vector <trie> t;
queue <int> q;
stack <int> inv;

void ins(char p[], int index)
{
    int n=strlen(p);
    int nod = 0;
    for(int i=0;i<n;i++)
    {
        if(t[nod].fii[car(p[i])]==-1)
        {
            trie aux;
            t[nod].fii[car(p[i])]=t.size();
            t.push_back(aux);
        }
        nod=t[nod].fii[car(p[i])];
    }
    t[nod].ind.push_back(index);
}
void bfs()
{
    queue <int> q;

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

    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inv.push(u);
        for(int i=0;i<26;i++)
            if(t[u].fii[i]!=-1)
            {
                int suffix = t[u].suffix_link;

                while(t[suffix].fii[i]==-1 && suffix!=0)
                    suffix = t[suffix].suffix_link;

                if(t[suffix].fii[i]!=-1)
                    t[t[u].fii[i]].suffix_link = t[suffix].fii[i];
                else t[t[u].fii[i]].suffix_link = 0;

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

void ahoaho(char c[])
{
    int n = strlen(c);
    int nod = 0;
    for(int i=0;i<n;i++)
    {
        while(t[nod].fii[car(c[i])]==-1 && nod!=0)
            nod = t[nod].suffix_link;

        if(t[nod].fii[car(c[i])]!=-1)   nod = t[nod].fii[car(c[i])];

        t[nod].cnt++;
    }
}

void antibfs()
{
    while(!inv.empty())
    {
        int u=inv.top();
        inv.pop();
        if(t[u].suffix_link!=-1) t[t[u].suffix_link].cnt += t[u].cnt;

        for(auto it:t[u].ind)
            ap[it]+=t[u].cnt;
    }
}
int main()
{
    trie root;
    t.push_back(root);

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

    bfs();
    ahoaho(c);
    antibfs();

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