Cod sursa(job #3288948)

Utilizator Anul2024Anul2024 Anul2024 Data 24 martie 2025 21:22:56
Problema Aho-Corasick Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <cstring>
#define dim 10000
#define si short int
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
int n,qr,m,f,l,sol[dim+1];
char str[100*dim+2],s[dim+2];
struct trie
{
    trie *nxt[26],*fb;
    char pos;
    int sol;
    trie ()
    {
        for (int i=0; i<26; i++)
            nxt[i]=NULL;
        fb=NULL;
        pos=sol=0;
    }
};
trie *r=new trie;
trie* q[100*dim+2];
void add (trie *r,char s[],int n,char pos)
{
    for (int i=0; i<n; i++)
    {
        if (r->nxt[(si)s[i]]==NULL)
            r->nxt[(si)s[i]]=new trie;
        r=r->nxt[(si)s[i]];
    }
    r->pos=pos;
}
void calc_fb (trie *r)
{
    q[l]=r;
    r->fb=r;
    while (f<=l)
    {
        trie *p=q[f++];
        for (int i=0; i<26; i++)
        {
            if (p->nxt[i]!=NULL)
            {
                q[++l]=p->nxt[i];
                if (p!=r)
                {
                    trie *pos=p->fb;
                    while (pos!=r&&pos->nxt[i]==NULL)
                        pos=pos->fb;
                    if (pos->nxt[i]!=NULL)
                        pos=pos->nxt[i];
                    p->nxt[i]->fb=pos;
                }
                else
                    p->nxt[i]->fb=r;
            }
        }
    }
}
void solve (trie *r,char s[],int n)
{
    trie *p=r;
    for (int i=0; i<n; i++)
    {
        while (p!=r&&p->nxt[(si)s[i]]==NULL)
            p=p->fb;
        if (p->nxt[(si)s[i]]!=NULL)
        {
            p=p->nxt[(si)s[i]];
            p->sol++;
        }
    }
}
void propagate ()
{
    for (int i=l; i>0; i--)
    {
        if (q[i]->pos!=0)
            sol[(si)q[i]->pos]+=q[i]->sol;
        if (q[i]->fb!=r)
            q[i]->fb->sol+=q[i]->sol;
    }
}
void read ()
{
    fin>>str;
    n=strlen (str);
    for (int i=0; i<n; i++)
        str[i]-='a';
    fin>>qr;
    for (int i=1; i<=qr; i++)
    {
        fin>>s;
        m=strlen (s);
        for (int j=0; j<m; j++)
            s[j]-='a';
        add (r,s,m,i);
    }
}
void print ()
{
    for (int i=1; i<=qr; i++)
        fout<<sol[i]<<"\n";
}
int main()
{
    read ();
    calc_fb (r);
    solve (r,str,n);
    propagate ();
    print ();
    return 0;
}