Cod sursa(job #2515422)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 28 decembrie 2019 15:50:58
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <bits/stdc++.h>
#define DIMM 1000010
#define DIM_CUV 10010
#define DIM 110
using namespace std;

FILE *fin = fopen ("ahocorasick.in","r");
FILE *fout = fopen ("ahocorasick.out","w");

struct trie{
    trie *f[26];
    trie *back; /// nodul care se duce in sus
    vector <trie*> v;
    int cnt;
    trie(){
        back = 0;
        cnt = 0;
        memset (f,0,sizeof f);
    }
};
trie *rad = new trie;
trie *sol[DIM];
char v[DIMM],s[DIM_CUV];
int n,m,i,j;
deque <trie*> c;
void add_trie (trie *rad, char *s){
    if (*s == 0){
        /// inseamna ca am ajuns la final
        sol[i] = rad;
        return;
    }
    if (!rad->f[*s-'a']) /// trb sa adaug litera
        rad->f[*s-'a'] = new trie;
    add_trie (rad->f[*s-'a'],s+1); /// tec la urmatoarea litera
}
void dfs (trie *nod){
    for (int i=0;i<nod->v.size();++i){
        dfs (nod->v[i]);
        nod->cnt += nod->v[i]->cnt;
    }
}
int main (){

    fscanf (fin,"%s\n",v+1); /// sirul mare

    /// construiesc trie ul cu toate cuvintele
    fscanf (fin,"%d\n",&n);
    for (i=1;i<=n;++i){
        fscanf (fin,"%s\n",s);
        add_trie (rad,s);
    }
    /// acum trebuie sa fac bfs pe trie ca sa determin acele muchii de intoarcere
    c.push_back(rad);
    while (!c.empty()){
        trie *nod = (trie *)c.front();
        c.pop_front();
        for (i=0;i<=25;++i){
            if (!nod->f[i])
                continue;
            /// ma duc in sus cat timp nu dau de litera care imi trebuie
            trie *aux = nod->back;
            while (aux != NULL && aux->f[i] == NULL)
                aux = aux->back;

            if (aux == NULL){ /// nu am gasit nimic, deci leg de radacina
                nod->f[i]->back = rad;
            } else nod->f[i]->back = aux->f[i];

            nod->f[i]->back->v.push_back(nod->f[i]);
            c.push_back(nod->f[i]);
        }}

    /// acum trb sa parcurg sirul principal
    m = strlen (v+1);
    trie *nod = rad;
    for (i=1;i<=m;++i){
        int val = v[i] - 'a';
        while (nod != rad && nod->f[val] == NULL)
            nod = nod->back;

        if (nod->f[val] != NULL){
            nod = nod->f[val];
            ++nod->cnt;
        }
    }
    /// dfs din radacina pt sume partiale
    dfs (rad);
    for (i=1;i<=n;++i)
        fprintf(fout,"%d\n",sol[i]->cnt);

    return 0;
}