Cod sursa(job #2302678)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 15 decembrie 2018 00:34:56
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
#define LA 1000001
#define LB 10001
#define ch c[k]-'a'

using namespace std;

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

string s, c;
int n, st, dr, ans[105];

struct Trie{

    int n0;
    vector <int> ind;

    Trie *fii[26], *fail;

    Trie(){

        n0 = 0;
        fail = NULL;
        memset(fii, NULL, sizeof(fii));

    }


};
Trie *T, *q[LB];

void Insert(Trie *nod, int k, int poz)
{
    if(c[k] == '\0')
    {
        nod->ind.push_back(poz);
        return;
    }
    int next = c[k]-'a';
    if(nod->fii[next] == NULL) nod->fii[next] = new Trie;

    Insert(nod->fii[next], k+1, poz);


}

void BFS(Trie *t)
{
    st = dr = 1;
    t->fail = t;

    for(q[st] = t; st <= dr; st++)
    {
        Trie *f = q[st];
        for(int i = 0; i < 26; i++)
        {
            if(f->fii[i] == NULL)
                continue;
            Trie *d;
            for(d = f->fail; d->fii[i] == NULL && d!=t; d = d->fail);

            if(d->fii[i] != NULL && d->fii[i] != f->fii[i]) d = d->fii[i];

            f->fii[i]->fail = d;

            q[++dr] = f->fii[i];

        }

    }
    t->fail = NULL;


}

void BFT(Trie *t)
{
    Trie *f;
    for(int i = dr; i >0; i--)
    {
        f = q[i];

        if(f->fail != NULL) f->fail->n0 += f->n0;

        for(int j = 0; j < f->ind.size(); j++)
            ans[f->ind[j]] = f->n0;


    }

}

int main()
{
    fin >> s;
    fin >> n;
    T = new Trie;
    Trie *g;
    for(int i = 1; i <= n; i++)
    {
        fin >> c;
        Insert(T, 0, i);
    }

    BFS(T);

   g = T;
    for(int i = 0; i < s.size(); i++)
    {
        int next = s[i] - 'a';

        for(; g->fii[next] == NULL && g != T; g = g->fail);

        if(g->fii[next] != NULL) g = g->fii[next];
        g->n0++;
    }
    BFT(T);

    for(int i = 1; i <= n; i++)
        fout << ans[i] << '\n';


    return 0;
}