Cod sursa(job #3155061)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 7 octombrie 2023 11:40:24
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
string str;
int n,sol[105];
vector<vector<int>> who;
vector<int> empvec;
int go(int,int);
int getsuf(int);
int getdict(int);
struct node
{
    int lit;
    int go[26];
    int suflink;
    int dictlink;
    int par;
    node()
    {
        for(int i=0;i<26;i++)
            go[i]=-1;
        suflink=-1;
        dictlink=-1;
    }
};
node emp;
vector<node> t;
void addstring(string s,int ind)
{
    int me=0;
    for(char c:s)
    {
        int lit=c-'a';
        if(t[me].go[lit]==-1)
        {
            t[me].go[lit]=t.size();
            node x=emp;
            x.lit=lit;
            x.par=me;
            t.push_back(x);
            who.push_back(empvec);
        }
        me=t[me].go[lit];
    }
    who[me].push_back(ind);
}
int go(int nod,int lit)
{
    if(t[nod].go[lit]!=-1)
        return t[nod].go[lit];
    if(nod==0)
        return 0;
    t[nod].go[lit]=go(getsuf(nod),lit);
    return t[nod].go[lit];
}
int getsuf(int nod)
{
    if(t[nod].suflink!=-1)
        return t[nod].suflink;
    if(nod==0||t[nod].par==0)
        return 0;
    t[nod].suflink=go(getsuf(t[nod].par),t[nod].lit);
    return t[nod].suflink;
}
int getdict(int nod)
{
    if(t[nod].dictlink!=-1)
        return t[nod].dictlink;
    if(nod==0)
        return 0;
    if(who[getsuf(nod)].size()>0)
        t[nod].dictlink=getsuf(nod);
    else
        t[nod].dictlink=getdict(getsuf(nod));
    return t[nod].dictlink;
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    t.push_back(emp);
    who.push_back(empvec);
    fin>>str;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        string a;
        fin>>a;
        addstring(a,i);
    }
    int me=0;
    for(int i=0;i<str.size();i++)
    {
        int lit=str[i]-'a';
        me=go(me,lit);
        int aux=me;
        while(aux!=0)
        {
            for(int j:who[aux])
                sol[j]++;
            aux=getdict(aux);
        }
    }
    for(int i=1;i<=n;i++)
        fout<<sol[i]<<'\n';
    return 0;
}