Cod sursa(job #1971307)

Utilizator vladm98Munteanu Vlad vladm98 Data 20 aprilie 2017 10:49:19
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;
char s[1000002];
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
struct Trie
{
    int nr;
    Trie *fail;
    Trie *child[27];
    Trie ()
    {
        nr = 0;
        fail = NULL;
        for (int i = 1; i<=26; ++i)
            child[i] = NULL;
    }
};
Trie *radacina, *Capat[101], *Q[1000555];
void baga (Trie *& node, int indice)
{
    char c;
    c = fin.get();
    if (c<'a' || c>'z')
    {
        Capat[indice] = node;
        return;
    }
    int poz = c-'a'+1;
    if (node->child[poz] == NULL)
        node->child[poz] = new Trie();
    baga(node->child[poz], indice);
}
int main()
{
    radacina = new Trie();
    fin >> (s+1);
    int n;
    fin >> n;
    fin.get();
    for (int i = 1; i<=n; ++i)
        baga(radacina, i);
    radacina->fail = radacina;
    int p = 1;
    int u = 1;
    Q[p] = radacina;
    while (p<=u)
    {
        Trie *node = Q[p];
        for (int i = 1; i<=26; ++i)
        {
            if (node->child[i] == NULL) continue;
            Trie *suf = node->fail;
            while (suf->child[i] == NULL && suf!=radacina)
                suf = suf->fail;
            if (suf->child[i]!=NULL && suf->child[i] != node->child[i])
                node->child[i]->fail = suf->child[i];
            else node->child[i]->fail = radacina;
            Q[++u] = node->child[i];
        }
        ++p;
    }
    int copie = n;
    n = strlen(s+1);
    Trie *unde = radacina;
    for (int i = 1; i<=n; ++i)
    {
        int poz = s[i]-'a'+1;
        while (unde!=radacina && unde->child[poz]==NULL)
            unde = unde->fail;
        if (unde->child[poz]!=NULL)
            unde = unde->child[poz];
        unde->nr++;
    }
    for (int i = u; i>=1; --i)
        Q[i]->fail->nr+=Q[i]->nr;
    for (int i = 1; i<=copie; ++i)
        fout << Capat[i]->nr << '\n';
    return 0;
}