Cod sursa(job #3204014)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 15 februarie 2024 13:09:59
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.55 kb
#include <fstream>
#include <vector>
const int NMAX=1e6+5;

using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

struct node
{
    int next[26], tran[26];
    int fath, ch, link;
    node()
    {
        int i;
        for(i=0; i<26; i++)
            next[i]=tran[i]=-1;
        link=-1; fath=ch=-1;
    }
};

vector <node> trie;
vector <int> st, fans;
int dp[NMAX]; ///nr de terminatii ale cuvintelor
char s[NMAX], t[NMAX];

void trie_insert(char *);
void build_aho_corasick();
int pi(int); ///sufflink aka muchii cu epsilon
int sigma(int, int); ///tran aka iti duce la capatul celor cu epsilon
void pls_solve(char *);

int main()
{
    int i, n;
    fin>>s;
    node root;
    trie.push_back(root);
    fin>>n;
    for(i=0; i<n; i++)
    {
        fin>>t;
        trie_insert(t);
    }
    build_aho_corasick();
    pls_solve(s);
    for(i=0; i<n; i++) fout<<dp[fans[i]]<<'\n';
    return 0;
}

void trie_insert(char *s)
{
    node new_node;
    int node=0, i;
    for(i=0; s[i]; i++)
    {
        if(trie[node].next[s[i]-'a']==-1)
        {
            new_node.fath=node;
            new_node.ch=s[i]-'a';
            trie.push_back(new_node);
            trie[node].next[s[i]-'a']=trie.size()-1;
        }
        node=trie[node].next[s[i]-'a'];
    }
    fans.push_back(node);
}

void build_aho_corasick()
{
    int i, j;
    for(i=0; i<int(trie.size()); i++)
    {
        pi(i);
        for(j=0; j<26; j++) sigma(i, j);
    }
}

int pi(int node)
{
    if(trie[node].link==-1)
    {
        if(!node || !trie[node].fath)
            trie[node].link=0;
        else trie[node].link=sigma(pi(trie[node].fath), trie[node].ch);
    }
    return trie[node].link;
}

int sigma(int node, int ch)
{
    if(trie[node].tran[ch]==-1)
    {
        if(trie[node].next[ch]!=-1)
            trie[node].tran[ch]=trie[node].next[ch];
        else if(node) trie[node].tran[ch]=sigma(pi(node), ch);
        else trie[node].tran[ch]=0;
    }
    return trie[node].tran[ch];
}

void pls_solve(char *s)
{
    int node=0, i, j;
    for(i=0; s[i]; i++)
    {
        node=trie[node].tran[s[i]-'a'];
        dp[node]++;
    }
    st.push_back(0);
    for(i=0; i<int(st.size()); i++)
    {
        node=st[i];
        for(j=0; j<26; j++)
        {
            if(trie[node].next[j]!=-1)
                st.push_back(trie[node].next[j]);
        }
    }
    for(i=int(st.size())-1; i>=0; i--)
    {
        node=st[i];
        dp[trie[node].link]+=dp[node];
    }
}