Cod sursa(job #3180267)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 4 decembrie 2023 21:52:08
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
char txt[1000001],word[10001];
struct Trie
{
    Trie *fiu[26],*suffix,*output;
    bool ok=false;
    int nrap=0;
}*rez[101];
Trie *root=new Trie;
void startup(Trie *nod)
{
    for(int i=0;i<26;i++)
        nod->fiu[i]=NULL;
}
void out(Trie *nod)
{
    if(nod!=root)
    {
        nod->nrap++;
        out(nod->output);
    }
}
Trie *suf(Trie *nod, int ch)
{
    if(nod->fiu[ch]!=NULL)
        return nod->fiu[ch];
    else
    if(nod!=root)
        return suf(nod->suffix,ch);
    else
        return root;
}
Trie *coada[1000002];
Trie *add(Trie *nod, char *word)
{
    if(*word==NULL)
    {
        nod->ok=true;
        return nod;
    }
    else
    {
        if(nod->fiu[word[0]-'a']==NULL)
        {
            nod->fiu[word[0]-'a']=new Trie;
            startup(nod->fiu[word[0]-'a']);
        }
        return add(nod->fiu[word[0]-'a'],word+1);
    }
}
int main()
{
    int n,i,m;
    cin>>txt>>n;
    m=strlen(txt);
    startup(root);
    root->suffix=root;
    root->output=root;
    for(i=1;i<=n;i++)
    {
        cin>>word;
        rez[i]=add(root,word);
    }
    int j,t;
    for(t=0,j=0;t<26;t++)
        if(root->fiu[t]!=NULL)
        {
            coada[++j]=root->fiu[t];
            coada[j]->suffix=root;
        }
    for(i=1;i<=j;i++)
    {
        if(coada[i]->suffix->ok==true)
            coada[i]->output=coada[i]->suffix;
        else
            coada[i]->output=coada[i]->suffix->output;
        for(t=0;t<26;t++)
            if(coada[i]->fiu[t]!=NULL)
            {
                coada[++j]=coada[i]->fiu[t];
                coada[j]->suffix=suf(coada[i]->suffix,t);
            }
    }
    Trie *nodc=root;
    int ch;
    for(i=0;i<m;i++)
    {
        ch=txt[i]-'a';
        if(nodc->fiu[ch]!=NULL)
            nodc=nodc->fiu[ch];
        else
        {
            nodc=nodc->suffix;
            while(nodc->fiu[ch]==NULL&&nodc!=root)
                nodc=nodc->suffix;
            if(nodc->fiu[ch]!=NULL)
                nodc=nodc->fiu[ch];
        }
        nodc->nrap++;
        out(nodc->output);
    }
    for(i=1;i<=n;i++)
        cout<<rez[i]->nrap<<'\n';
    return 0;
}