Cod sursa(job #2921494)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 31 august 2022 13:54:56
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 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;
    int fiu[26],tata; 
    int fail;
    int green;
    Trie(int daddy){
        for(int i=0;i<26;i++)
            fiu[i]=-1;
        fail=-1;
        tata=daddy;
        exis=0;
    }
};
queue <int> coada;
vector <Trie> copac;
void baga(int nod,char a[],int poz)
{
    if(a[0]==0)
    {
        copac[nod].care.push_back(poz);
        copac[nod].exis=1;
        return;
    }
    if(copac[nod].fiu[a[0]-'a']==-1)
    {
        Trie urm(nod);
        copac.push_back(urm);
        copac[nod].fiu[a[0]-'a']=copac.size()-1;
    }
    baga(copac[nod].fiu[a[0]-'a'],a+1,poz);
}
char a[10001];
int main()
{
    int i,q;
    in>>s;
    in>>q;
    Trie root(-1);
    copac.push_back(root);
    for(i=1;i<=q;i++)
    {
        in>>a;
        //out<<(int)a[strlen(a)]<<'\n';
        baga(0,a,i);
    }
    for(i=0;i<26;i++)
        if(copac[0].fiu[i]==-1)
            copac[0].fiu[i]=0;
        else
        {
            coada.push(copac[0].fiu[i]);
            copac[copac[0].fiu[i]].fail=0;
            copac[copac[0].fiu[i]].green=0;
        }
    while(coada.size())
    {
        int cur=coada.front();
        coada.pop();
        for(i=0;i<26;i++)
            if(copac[cur].fiu[i]!=-1)
            {
                coada.push(copac[cur].fiu[i]);
                int inc=copac[cur].fail;
                while(copac[inc].fiu[i]==-1)
                    inc=copac[inc].fail;
                copac[copac[cur].fiu[i]].fail=copac[inc].fiu[i];
                if(copac[copac[inc].fiu[i]].exis)
                    copac[copac[cur].fiu[i]].green=copac[inc].fiu[i];
                else
                    copac[copac[cur].fiu[i]].green=copac[copac[inc].fiu[i]].green;
            }
    }
    int start=0;
    copac[0].green=0;
    for(i=0;i<s.size();i++)
    {
        while(copac[start].fiu[s[i]-'a']==-1)
            start=copac[start].fail;
        start=copac[start].fiu[s[i]-'a'];
        int interes=start;
        if(!copac[interes].exis)
            interes=copac[interes].green;
        while(interes)
        {
            for(auto it:copac[interes].care)
                ap[it]++;
            interes=copac[interes].green;
        }
    }
    for(i=1;i<=q;i++)
        out<<ap[i]<<'\n';
    return 0;
}