Cod sursa(job #2408045)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 17 aprilie 2019 15:52:36
Problema Aho-Corasick Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include<bits/stdc++.h>

using namespace std;

const int sigma=26;
const int maxN=(1e2)+5;

inline int f(int i)
{
    return i-'a'+1;
}

struct trie
{
    int sol;
    trie *sons[sigma+5];
    trie *fail;
    vector<trie*> v; //numarul de noduri din trie care au fail-ul in nodul curent
    trie()
    {
        sol=0;
        for(int i=0;i<=sigma;i++)
            sons[i]=NULL;
        fail=NULL;
        v.clear();
    }
}*root=new trie();

trie *w[maxN];

inline trie* Insert(trie *node,char *s)
{
    if(*s==NULL)
    {
        return node;
    }
        else
    {
        if(!node->sons[f(s[0])]) node->sons[f(s[0])]=new trie();
        return Insert(node->sons[f(s[0])],s+1);
    }
}

inline void dfs(trie *node)
{
    for(auto it:node->v)
    {
        dfs(it);
        node->sol+=it->sol;
    }
}

char str[maxN],s[maxN];
int n,m;
deque<trie*> q;
trie* aux;

int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);

    scanf("%s",str);

    m=strlen(str);

    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        w[i]=Insert(root,s);
    }

    q.push_back(root);

    while(!q.empty())
    {
        trie *node=q.front();
        q.pop_front();
        for(int i=1;i<=26;i++)
        {
            if(node->sons[i])
            {
                aux=node->fail;
                while(aux && aux->sons[i]==NULL) aux=aux->fail;
                if(aux==NULL) node->sons[i]->fail=root;
                    else node->sons[i]->fail=aux->sons[i];
                node->sons[i]->fail->v.push_back(node->sons[i]);
                q.push_back(node->sons[i]);
            }
        }
    }

    aux=root;
    for(int i=0;i<m;i++)
    {
        while(aux!=root && aux->sons[f(str[i])]==NULL) aux=aux->fail;
        if(aux->sons[f(str[i])]!=NULL) aux=aux->sons[f(str[i])];
        aux->sol++;
    }

    dfs(root);

    for(int i=1;i<=n;i++)
        printf("%d\n",w[i]->sol);

    return 0;
}