Cod sursa(job #988013)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 21 august 2013 19:30:34
Problema Aho-Corasick Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <string.h>

#define maxwordlen 10001
#define maxtextlen 1000001

using namespace std;

ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

struct trie_node
{
    short which;
    int nr;
    trie_node *s[25],*fail;

    trie_node ()
    {
        which=0;
        nr=0;
        for (int i=0; i<25; ++i) s[i]=NULL;
        fail=NULL;
    }
}*trie,*q[100*maxwordlen];

char word[maxwordlen],text[maxtextlen];
int v[101],wordlen,textlen,i,s,l,n;


void trie_insert (trie_node *current, int j)
{
    if (j==wordlen) {current->which=i; return;}

    int letter = word[j] - 'a';

    if (current->s[letter]==NULL) current->s[letter] = new trie_node;

    trie_insert (current->s[letter],j+1);
}

void bfs ()
{
    s=1,l=1;

    q[l] = trie;
    trie->fail = trie;

    while (s <= l)
    {
        for (int i=0; i<25; ++i)
            if (q[s]->s[i] != NULL)
            {
                 trie_node *back=q[s]->fail;
                 while (back!=trie && back->s[i]==NULL) back = back->fail;

                 if (back->s[i]!=NULL && back!=q[s]) back = back->s[i];
                 q[s]->s[i]->fail=back;

                 q[++l] = q[s]->s[i];
            }
        ++s;
    }
}

void antibfs ()
{
    for (int i=l; i>=1; --i)
    {
        q[i]->fail->nr += q[i]->nr;
        v[q[i]->which] = q[i]->nr;
    }
}

int main()
{
    trie = new trie_node;

    fin>>text;

    fin>>n;
    for (i=1; i<=n; ++i)
    {
        fin>>word;
        wordlen = strlen (word);

        trie_insert (trie,0);
    }

    bfs ();

    textlen = strlen (text);
    trie_node *current = trie;

    for (int i=0; i<textlen; ++i)
    {
        int letter = text[i]-'a';

        while (current->s[letter]==NULL && current!=trie) current = current->fail;
        if (current->s[letter]!=NULL)
        {
            current = current->s[letter];
            current->nr++;
        }
    }

    antibfs();

    for (int i=1; i<=n; ++i) fout<<v[i]<<"\n";
}