Cod sursa(job #2921478)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 31 august 2022 13:01:32
Problema Aho-Corasick Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
string s;
int ap[101];
struct Trie{
    bool exis;
    vector <int> care;
    Trie *fiu[26],*tata; 
    Trie *fail;
    Trie *green;
    Trie(Trie *daddy){
        for(int i=0;i<26;i++)
            fiu[i]=NULL;
        fail=NULL;
        tata=daddy;
        exis=0;
    }
};
queue <Trie*> coada;
Trie *root=new Trie(NULL);
void baga(Trie *nod,char a[],int poz)
{
    if(a[0]==0)
    {
        nod->care.push_back(poz);
        nod->exis=1;
        return;
    }
    if(nod->fiu[a[0]-'a']==NULL)
    {
        Trie *urm=new Trie(nod);
        nod->fiu[a[0]-'a']=urm;
    }
    baga(nod->fiu[a[0]-'a'],a+1,poz);
}
char a[10001];
int main()
{
    int i,q;
    in>>s;
    in>>q;
    for(i=1;i<=q;i++)
    {
        in>>a;
        //out<<(int)a[strlen(a)]<<'\n';
        baga(root,a,i);
    }
    for(i=0;i<26;i++)
        if(root->fiu[i]==NULL)
            root->fiu[i]=root;
        else
        {
            coada.push(root->fiu[i]);
            root->fiu[i]->fail=root;
            root->fiu[i]->green=root;
        }
    while(coada.size())
    {
        Trie *cur=coada.front();
        coada.pop();
        for(i=0;i<26;i++)
            if(cur->fiu[i]!=NULL)
            {
                coada.push(cur->fiu[i]);
                Trie *inc=cur->fail;
                while(inc->fiu[i]==NULL)
                    inc=inc->fail;
                cur->fiu[i]->fail=inc->fiu[i];
                if(inc->fiu[i]->exis)
                    cur->fiu[i]->green=inc->fiu[i];
                else
                    cur->fiu[i]->green=inc->fiu[i]->green;
                if(cur->fiu[i]->exis)
                    for(auto it:cur->fiu[i]->green->care)
                        cur->fiu[i]->care.push_back(it);
            }
    }
    Trie *start=root;
    root->green=root;
    for(i=0;i<s.size();i++)
    {
        while(start->fiu[s[i]-'a']==NULL)
            start=start->fail;
        start=start->fiu[s[i]-'a'];
        Trie *interes=start;
        if(!interes->exis)
            interes=interes->green;
        for(auto it:interes->care)
            ap[it]++;
    }
    for(i=1;i<=q;i++)
        out<<ap[i]<<'\n';
    return 0;
}