Cod sursa(job #2734976)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 1 aprilie 2021 18:04:37
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.09 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
string a;
int n;
bool use[1000005];
struct nod
{
    int muchii[29];
    char c;
    vector<int> leaf;
    int go[29];
    int suflink=-1,dict=-1;
    int parent;
};
nod emptynode;
vector<nod> t;
int sol[1005];
int go(int nod,char c);
int suflink(int nod);
int dict(int nod);
void add(string s,int index)
{
    int v=0;
    for(int i=0;i<s.size();i++)
    {
        char c=s[i];
        int lit=c-'a'+1;
        if(t[v].muchii[lit]==-1)
        {
            t[v].muchii[lit]=t.size();
            nod x=emptynode;
            x.c=c;
            x.parent=v;
            t.push_back(x);
        }
        v=t[v].muchii[lit];
        if(i+1==s.size())
            t[v].leaf.push_back(index);
    }
}
int suflink(int nod)
{
    if(t[nod].suflink!=-1)
        return t[nod].suflink;
    if(nod==0)
    {
        t[nod].suflink=0;
        return t[nod].suflink;
    }
    int p=t[nod].parent;
    if(p==0)
    {
        t[nod].suflink=0;
        return t[nod].suflink;
    }
    t[nod].suflink=go(suflink(p),t[nod].c);
    return t[nod].suflink;
}
int go(int nod,char c)
{
    int lit=c-'a'+1;
    if(t[nod].go[lit]!=-1)
        return t[nod].go[lit];
    if(t[nod].muchii[lit]!=-1)
    {
        t[nod].go[lit]=t[nod].muchii[lit];
        return t[nod].go[lit];
    }
    if(nod==0)
    {
        t[nod].go[lit]=0;
        return t[nod].go[lit];
    }
    t[nod].go[lit]=go(suflink(nod),c);
    return t[nod].go[lit];
}
int dict(int nod)
{
    if(t[nod].dict!=-1)
        return t[nod].dict;
    if(nod==0)
    {
        t[nod].dict=0;
        return t[nod].dict;
    }
    int nxt=suflink(nod);
    if(t[nxt].leaf.size())
    {
        t[nod].dict=nxt;
        return t[nod].dict;
    }
    t[nod].dict=dict(suflink(nod));
    return t[nod].dict;
}
void getleaf(int nod)
{
    use[nod]=1;
    int nxt=dict(nod);
    if(nxt==0)
        return;
    if(!use[nxt])
        getleaf(nxt);
    for(auto i:t[nxt].leaf)
        t[nod].leaf.push_back(i);
    sort(t[nod].leaf.begin(),t[nod].leaf.end());
    t[nod].leaf.erase(unique(t[nod].leaf.begin(),t[nod].leaf.end()),t[nod].leaf.end());
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin>>a>>n;
    emptynode.c='0';
    emptynode.dict=-1;
    emptynode.suflink=-1;
    for(int i='a';i<='z';i++)
    {
        emptynode.muchii[i-'a'+1]=-1;
        emptynode.go[i-'a'+1]=-1;
    }
    t.push_back(emptynode);
    for(int i=1;i<=n;i++)
    {
        string x;
        fin>>x;
        add(x,i);
    }
    for(int i=1;i<t.size();i++)
        getleaf(i);
    int v=0;
    for(auto c:a)
    {
        v=go(v,c);
        for(auto i:t[v].leaf)
            sol[i]++;
        int aux=v;
        /*while(dict(aux)>0)
        {
            aux=dict(aux);
            for(auto i:t[aux].leaf)
                sol[i]++;
        }*/
    }
    for(int i=1;i<=n;i++)
        fout<<sol[i]<<'\n';
    return 0;
}