Cod sursa(job #2897937)

Utilizator stefantagaTaga Stefan stefantaga Data 5 mai 2022 14:35:47
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.22 kb
#include <bits/stdc++.h>

using namespace std;
struct Aho_Corasick
{
    int indice=0;
    int go[26];
    int urm[26];
    int parinte = -1;
    int pch=0;
    int link=-1;
    int urmdinsir=0;
    Aho_Corasick(int Parent =-1,int PCH = -1)
    {
        parinte = Parent;
        pch = PCH;
        for (int i=0; i<=26; i++)
        {
            go[i]=urm[i]=-1;
        }
    }
};
vector <Aho_Corasick> V(1);
void add_string(string s2,int UndeSunt)
{
    int acum = 0;
    for (int j=0; j<s2.size(); j++)
    {
        int loc = s2[j]-'a';
        if (V[acum].urm[loc]==-1)
        {
            V[acum].urm[loc]=V.size();
            Aho_Corasick salut = Aho_Corasick(acum,loc);
            salut.parinte=acum;
            salut.pch=loc;
            V.push_back(salut);
        }
        acum = V[acum].urm[loc];
    }
    V[acum].indice= UndeSunt;
}
int n,i,sol[100005];
string s,s2;
int go(int v,int ch);

int get_link(int v)
{
    if (V[v].link==-1)
    {
        if (v==0||V[v].parinte==0)
        {
            V[v].link=0;
        }
        else
        {
            V[v].link=go(get_link(V[v].parinte),V[v].pch);
        }
    }
    return V[v].link;
}

int go(int v,int ch)
{
    if (V[v].go[ch]==-1)
    {
        if (V[v].urm[ch]!=-1)
        {
            V[v].go[ch]=V[v].urm[ch];
        }
        else
        {
            if (v==0)
            {
                V[v].go[ch]=0;
            }
            else
            {
                V[v].go[ch]=go(get_link(v),ch);
            }
        }
    }
    return V[v].go[ch];
}
int fr[1000005];
int main()
{
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>s;
    cin>>n;
    for (i=1; i<=n; i++)
    {
        cin>>s2;
        add_string(s2,i);
    }
    for (int j=0; j<V.size(); j++)
    {
        for (int k=0; k<26; k++)
        {
            go(j,k);
        }
    }
    queue <int> q;
    q.push(0);
    while (!q.empty())
    {
        int acum = q.front();
        fr[acum]=0;
        q.pop();
        int spate= V[acum].link;
        auto salut = V[spate];
        auto Acum = V[acum];
        if (spate!=-1)
        {
            if (V[spate].indice!=0)
            {
                V[acum].urmdinsir=spate;
            }
            else
            {
                V[acum].urmdinsir = V[spate].urmdinsir;
            }
        }
        for (int j=0; j<26; j++)
        {
            int Urm = V[acum].urm[j];
            if (Urm!=-1)
            {
                if (fr[Urm]==0)
                {
                    fr[Urm]=1;
                    q.push(Urm);
                }
            }
        }
    }
    int acum = 0;
    for (int j=0; j<s.size(); j++)
    {
        acum=go(acum,s[j]-'a');
        int copie=acum;
        if (V[copie].indice==0)
        {
            copie = V[copie].urmdinsir;
        }
        if (copie>0&&V[copie].indice!=0)
        {
            while (copie>0)
            {
                sol[V[copie].indice]++;
                copie=V[copie].urmdinsir;
            }
        }
    }
    for (i=1; i<=n; i++)
    {
        cout<<sol[i]<<'\n';
    }
    return 0;
}