Cod sursa(job #1686017)

Utilizator touristGennady Korotkevich tourist Data 11 aprilie 2016 23:41:18
Problema Aho-Corasick Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <bits/stdc++.h>
#define Nmax 1000005
#define pb push_back

using namespace std;

char a[Nmax],s[Nmax];
int n,l;

struct Trie
{
    Trie *leg[26],*suf;
    int cnt;
    bool viz;
    vector <Trie*> L;
    Trie()
    {
        for(int i=0;i<26;++i) leg[i]=0;
        cnt=0; L.clear(); viz=0;
    }
} *rad = new Trie(),*wh[105];
queue <Trie*> Q;

inline void Add(Trie *nod, int p, int ind)
{
    if(p==l+1)
    {
        wh[ind]=nod; return;
    }
    if(!nod->leg[s[p]-'a']) nod->leg[s[p]-'a']=new Trie();
    Add(nod->leg[s[p]-'a'],p+1,ind);
}

inline void Make_Suf()
{
    int i;
    Trie *nod,*node;
    for(i=0;i<26;++i)
        if(rad->leg[i])
        {
            rad->leg[i]->suf=rad;
            rad->L.pb(rad->leg[i]);
            Q.push(rad->leg[i]);
        }
    while(!Q.empty())
    {
        nod=Q.front(); Q.pop();
        for(i=0;i<26;++i)
            if(nod->leg[i])
            {
                node=nod->suf;
                while(node!=rad && !node->leg[i]) node=node->suf;
                if(node->leg[i]) node=node->leg[i];
                nod->leg[i]->suf=node;
                node->L.pb(nod->leg[i]);
                Q.push(nod->leg[i]);
            }
    }
}

inline void Dfs(Trie *nod)
{
    nod->viz=1;
    for(auto it : nod->L)
    {
        if(!it->viz) Dfs(it);
        nod->cnt+=it->cnt;
    }
}

int main()
{
    int m,i;
    ifstream cin("ahocorasick.in");
    ofstream cout("ahocorasick.out");
    cin>>(a+1)>>m; n=strlen(a+1);
    for(i=1;i<=m;++i)
    {
        cin>>(s+1); l=strlen(s+1);
        Add(rad,1,i);
    }
    Make_Suf();
    Trie *nod = rad;
    for(i=1;i<=n;++i)
    {
        while(!nod->leg[a[i]-'a']) nod=nod->suf;
        if(nod->leg[a[i]-'a']) nod=nod->leg[a[i]-'a'];
        nod->cnt++;
    }
    for(i=1;i<=m;++i)
    {
        if(!wh[i]->viz) Dfs(wh[i]);
        cout<<wh[i]->cnt<<"\n";
    }
    return 0;
}