Cod sursa(job #2918750)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 12 august 2022 20:05:33
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>
#define N 10005
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct Trie
{
    int cnt;
    vector<int>curent;
    Trie *fiu[26],*fail;
    Trie()
    {
        cnt=0;fail=0;
        memset(fiu,0,sizeof(fiu));
    }
};
Trie *T=new Trie;
int sol[N],n;
char text[1000005];
void Adaugare(Trie *T,char *s,int i)
{
    if(*s==NULL) {T->curent.push_back(i);return;}
    if(!T->fiu[*s-'a']) T->fiu[*s-'a']=new Trie;
    Adaugare(T->fiu[*s-'a'],s+1,i);
}
queue<Trie*>q;
stack<Trie*>stv;
void bfs(Trie *T)
{
    Trie *p;
    T->fail=T;
    q.push(T);
    while(!q.empty())
    {
        Trie *u=q.front();
        q.pop();
        stv.push(u);
        for(int i=0;i<26;i++)
            if(u->fiu[i])
        {
            for(p=u->fail;p!=T&&!p->fiu[i];p=p->fail);
            if(p->fiu[i]&&p->fiu[i]!=u->fiu[i]) p=p->fiu[i];
            u->fiu[i]->fail=p;
            q.push(u->fiu[i]);
        }
    }
    T->fail=NULL;
}
void ahoaho(char *s)
{
    Trie *p=T;
    for(int i=0;s[i];i++)
    {
        for(;!p->fiu[s[i]-'a']&&p!=T;p=p->fail);
        if(p->fiu[s[i]-'a']) p=p->fiu[s[i]-'a'];
        p->cnt++;
    }
}
void antibfs(Trie *T)
{
    while(!stv.empty())
    {
        Trie *u=stv.top();
        stv.pop();
        if(u->fail) u->fail->cnt+=u->cnt;
        for(int i=0;i<u->curent.size();i++) sol[u->curent[i]]=u->cnt;
    }
}
int main()
{
    char s[N];
    fin>>text;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>s;
        Adaugare(T,s,i);
    }
    bfs(T);
    ahoaho(text);
    antibfs(T);
    for(int i=1;i<=n;i++) fout<<sol[i]<<"\n";
    return 0;
}