Cod sursa(job #2314600)

Utilizator dacianouaPapadia Mortala dacianoua Data 8 ianuarie 2019 20:22:39
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 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[1000005],words[105][10005];
int n;
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;
}