Cod sursa(job #3125444)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 3 mai 2023 10:46:52
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <bits/stdc++.h>
/*#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")*/
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
void addstring(int);
int go(int,int);
int getsuf(int);
int getdict(int);
string a,s;
int n;
struct aho
{
    char lit;
    int par;
    int go[27];
    int suflink,dictlink;
    vector<short> leaves;
} emp;
vector<aho> t;
int nodes,sol[105];
void addstring(int id)
{
    int cur=1;
    for(int i=0;i<s.size();i++)
    {
        int lit=s[i]-'a'+1;
        if(t[cur].go[lit]==0)
        {
            nodes++;
            t.push_back(emp);
            t[nodes].lit=s[i];
            t[nodes].par=cur;
            t[cur].go[lit]=nodes;
        }
        cur=t[cur].go[lit];
        if(i+1==s.size())
            t[cur].leaves.push_back(id);
    }
}
int go(int nod,int lit)
{
    if(t[nod].go[lit]!=0)
        return t[nod].go[lit];
    if(nod==1&&getsuf(nod)==1)
        return 1;
    t[nod].go[lit]=go(getsuf(nod),lit);
    return t[nod].go[lit];
}
int getsuf(int nod)
{
    if(nod==1)
        return 1;
    if(t[nod].par==1)
        return 1;
    if(t[nod].suflink!=0)
        return t[nod].suflink;
    t[nod].suflink=go(getsuf(t[nod].par),t[nod].lit-'a'+1);
    return t[nod].suflink;
}
int getdict(int nod)
{
    if(nod==1)
        return 1;
    if(t[nod].leaves.size()>=1)
        return nod;
    if(t[nod].dictlink!=0)
        return t[nod].dictlink;
    t[nod].dictlink=getdict(getsuf(nod));
    return t[nod].dictlink;
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fin>>a;
    fin>>n;
    nodes=1;
    t.push_back(emp);
    t.push_back(emp);
    t[1].lit='0';
    for(int i=1;i<=n;i++)
    {
        fin>>s;
        addstring(i);
    }
    int cur=1;
    for(int i=0;i<a.size();i++)
    {
        cur=go(cur,a[i]-'a'+1);
        int aux=cur;
        while(getdict(aux)!=1)
        {
            aux=getdict(aux);
            for(int j:t[aux].leaves)
                sol[j]++;
            aux=getsuf(aux);
        }
    }
    for(int i=1;i<=n;i++)
        fout<<sol[i]<<'\n';
    return 0;
}