Cod sursa(job #988021)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 21 august 2013 19:42:22
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <string.h>
#include <vector>

#define maxwordlen 10001
#define maxtextlen 1000001

using namespace std;

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

struct trie_node
{
    vector <short> which;
    int nr;
    trie_node *s[26],*fail;

    trie_node ()
    {
        nr=0;
        for (int i=0; i<26; ++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.push_back(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<26; ++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;
        for (int j=0; j<q[i]->which.size(); ++j) v[q[i]->which[j]] = 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";
}