Cod sursa(job #3331517)

Utilizator RaresPoinaruPoinaru-Rares-Aurel RaresPoinaru Data 28 decembrie 2025 20:20:57
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
#define cin fin
#define cout fout

const int SG=26;
const int MAXN=2e5+10;

int n,m;
string s;

struct Trie{
    Trie *f[SG];
    int rez;
    Trie *b;

    Trie (){
        for (int i=0;i<SG;++i) f[i]=nullptr;
        rez=0;
        b=nullptr;
    }
}*root,*v[MAXN];
stack <Trie *> st;

Trie *update (string a){
    Trie *trie=root;

    for (int i=0;i<a.size ();++i){
        int x=int (a[i]-'a');
        if (trie->f[x]==nullptr){
            trie->f[x]=new Trie;
        }
        trie=trie->f[x];
    }
    return trie;
}

void solve_backedge (Trie *trie, int i){
    Trie *bcrt=trie->b;
    while (bcrt!=root and bcrt->f[i]==nullptr)
        bcrt=bcrt->b;
    if (bcrt->f[i]!=nullptr and bcrt!=trie){
        trie->f[i]->b=bcrt->f[i];
    }
    else{
        trie->f[i]->b=root;
    }
}

void get_backedges (){
    queue <Trie *> q;
    root->b=root;
    q.push (root);
    while (!q.empty ()){
        Trie *trie=q.front ();
        st.push (trie);
        q.pop ();

        for (int i=0;i<SG;++i){
            if (trie->f[i]==nullptr) continue;

            solve_backedge (trie, i);
            q.push (trie->f[i]);
        }
    }

}

void solve (){
    Trie *trie=root;
    for (int i=0;i<m;++i){
        int x=int (s[i]-'a');
        while (trie!=root and trie->f[x]==nullptr)
            trie=trie->b;
        if (trie->f[x]){
            trie=trie->f[x];
        }
        trie->rez++;
    }

    while (!st.empty ()){
        trie=st.top ();
        st.pop ();
        trie->b->rez+=trie->rez;
    }
}

signed main()
{
    cin >>s;
    m=s.size ();
    cin >>n;
    root=new Trie;
    for (int i=1;i<=n;++i){
        string a;
        cin >>a;
        v[i]=update (a);
    }
    get_backedges ();
    solve ();
    for (int i=1;i<=n;++i){
        cout <<v[i]->rez<<'\n';
    }
    return 0;
}