Cod sursa(job #3225387)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 17 aprilie 2024 15:27:17
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <bits/stdc++.h>

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