Cod sursa(job #1061323)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 19 decembrie 2013 16:25:21
Problema Aho-Corasick Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include<stdio.h>
#include<vector>
#include<string.h>

using namespace std;

struct node
{
    int occ;
    node *next[30];
    node *back_step;
    node()
    {
        occ=0;
        for(int i=0;i<28;++i)next[i]=NULL;
    }
};

char text[1000001],words[100][10001];
int n,ans[101];
node *trie;
vector<node*>Q;

node* add_word(node* current_n,char *word,int ind)
{
    if(!current_n)current_n=new node;
    if(word[ind]=='\0')return current_n;
    current_n->next[word[ind]-'a']=add_word(current_n->next[word[ind]-'a'],word,ind+1);
    return current_n;
}

int get_occ(node* current_n,char *word,int ind)
{
    if(word[ind]=='\0')return current_n->occ;
    return get_occ(current_n->next[word[ind]-'a'],word,ind+1);
}

void create_aho()
{
    trie->back_step = trie;
    Q.push_back(trie);
    int ind=0;
    while(ind<Q.size())
    {
        for(int i=0;i<'z'-'a';++i)
        {
            node* next_n=Q[ind]->next[i];
            if(next_n)
            {
                Q.push_back(next_n);
                node *back=Q[ind]->back_step;
                while(back!=trie&&back->next[i]==NULL)back=back->back_step;
                if(back->next[i]!=NULL&&back->next[i]!=next_n)next_n->back_step=back->next[i];
                else next_n->back_step=trie;
            }
        }
        ind++;
    }
}

int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    gets(text);
    scanf("%d\n",&n);
    for(int i=0;i<n;++i)
    {
        gets(words[i]);
        trie = add_word(trie,words[i],0);
    }
    create_aho();
    int l=strlen(text);
    node *current_n=trie;
    for(int i=0;i<l;++i)
    {
        while(current_n!=trie&&current_n->next[text[i]-'a']==NULL)current_n=current_n->back_step;
        if(current_n->next[text[i]-'a']!=NULL)current_n=current_n->next[text[i]-'a'];
        current_n->occ++;
    }
    for(int i=Q.size()-1;i>=0;--i)
        Q[i]->back_step->occ+=Q[i]->occ;
    for(int i=0;i<n;++i)printf("%d\n",get_occ(trie,words[i],0));
    return 0;
}