Cod sursa(job #1581984)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 27 ianuarie 2016 15:10:27
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>

#define chr(x) (x - 'a')

using namespace std;

const int Ml = 1e6 + 7;
const int Mx = 1e4 + 5;
const int Mn = 1e2 + 3;

struct trie
{
    int cnt;
    trie *next[26],*fail;
    vector< trie* > vec;

    trie()
    {
        cnt = 0;
        fail = 0;
        memset(next,0,sizeof(next));
    }
};

int n,id;
char a[Ml],b[Mx];
queue< trie* > q;
trie *word[Mn],*root = new trie();

void add(trie *node,char *p)
{
    if (*p == 0)
    {
        word[id] = node;
        return;
    }

    if (node->next[chr(*p)] == 0)
        node->next[chr(*p)] = new trie();

    add(node->next[chr(*p)],p + 1);
}

void dfs(trie *node)
{
    for (auto aux : node->vec)
    {
        dfs(aux);
        node->cnt += aux->cnt;
    }
}

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

     scanf("%s\n%d",a,&n);

     int m = strlen(a);

     for (int i = 1;i <= n;i++)
     {
         scanf("%s\n",b);
         id = i;
         add(root,b);
     }

    q.push(root);

    while (!q.empty())
    {
        trie *node = q.front();
        q.pop();

        for (int i = 0;i < 26;i++)
            if (node->next[i])
            {
                trie *aux = node->fail;

                while (aux != 0 && aux->next[i] == 0)
                      aux = aux->fail;

                if (aux == 0)
                {
                    node->next[i]->fail = root;
                    root->vec.push_back(node->next[i]);
                }
               else
                {
                    node->next[i]->fail = aux->next[i];
                    aux->next[i]->vec.push_back(node->next[i]);
                }

                q.push(node->next[i]);
            }
    }

    trie *aux = root;

    for (int i = 0;i < m;i++)
    {
        while (aux != 0 && aux->next[chr(a[i])] == 0)
              aux = aux->fail;

        if (aux == 0)
           aux = root;
      else
           aux = aux->next[chr(a[i])];

        aux->cnt++;
    }

    dfs(root);

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

  return 0;
}