Cod sursa(job #3204144)

Utilizator aaagabiTurbinca Gabriel aaagabi Data 15 februarie 2024 19:02:07
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
typedef long long ll;
string a;
string dex[105];
int n,i;
vector <int> nodterm;
struct varf
{
    int next[26],tran[26];
    int link,tata,lit;
    bool terminal=false;
    varf()
    {
        for(int i=0;i<26;i++)
            next[i]=tran[i]=-1;
        tata=lit=link=-1;
    }
};
vector <varf> trie(1);
void addstring(string s)
{
    int nod=0;
    varf nou;
    for(auto ch:s)
    {
        int c=ch-'a';
        if(trie[nod].next[c]==-1)
        {
            nou.tata=nod;
            nou.lit=c;
            trie[nod].next[c]=trie.size();
            trie.push_back(nou);
        }
        nod=trie[nod].next[c];
    }
    trie[trie.size()-1].terminal=true;
    nodterm.push_back(nod);
}
int pi(int);
int sigma(int,int);
int dp[1000005];
ll ans=0;
void aho_corasick(string s)
{
    for(int i=0;i<trie.size();i++)
    {
        pi(i);
        for(int j=0;j<26;j++)
            sigma(i,j);
    }
    int nod=0;
    for(int i=0;i<=s.size();i++)
    {
        nod=trie[nod].tran[s[i]-'a'];
        dp[nod]++;
    }
    vector <int> parcurgere;
    parcurgere.push_back(0);
    for(int i=0;i<parcurgere.size();i++)
    {
        int nod=parcurgere[i];
        for(int j=0;j<26;j++)
            if(trie[nod].next[j]!=-1)
                parcurgere.push_back(trie[nod].next[j]);
    }
    reverse(parcurgere.begin(),parcurgere.end());
    for(int i:parcurgere)
    {
        dp[trie[i].link]+=dp[i];
    }
    for(int i:nodterm)
        fout<<dp[i]<<'\n';
}
int main()
{
    fin>>a;
    fin>>n;
    for(int i=1;i<=n;i++)
        {
            fin>>dex[i];
            addstring(dex[i]);
        }
    aho_corasick(a);
    return 0;
}
int pi(int nod)
{
    if(trie[nod].link==-1)
    {
        if(!nod||!trie[nod].tata)
            trie[nod].link=0;
        else
            trie[nod].link=sigma(pi(trie[nod].tata),trie[nod].lit);
    }
    return trie[nod].link;
}
int sigma(int nod,int lit)
{
    if(trie[nod].tran[lit]==-1)
    {
        if(trie[nod].next[lit]!=-1)
            trie[nod].tran[lit]=trie[nod].next[lit];
        else
        if(nod!=0)
            trie[nod].tran[lit]=sigma(pi(nod),lit);
        else
            trie[nod].tran[lit]=0;
    }
    return trie[nod].tran[lit];
}