Cod sursa(job #2515419)

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

ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
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 (){

    fin>>v+1; /// sirul mare
    /// construiesc trie ul cu toate cuvintele
    fin>>n;
    for (i=1;i<=n;i++){
        fin>>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++)
        fout<<sol[i]->cnt<<"\n";

    return 0;
}