Cod sursa(job #1546314)

Utilizator sebinechitasebi nechita sebinechita Data 7 decembrie 2015 22:04:08
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
#define MAX 1000010

char a[MAX], b[10010];
int st, dr, rez[102];
struct trie{
    int indice = 0;
    int nr = 0;
    trie *fiu[26] = {0}, *fail = 0;
} *T, *Q[MAX];

void introdu(trie *nod, char c[], int ind)
{
    if(c[0] == 0)
    {
        nod->indice = ind;
        return;
    }
    if(nod->fiu[c[0] - 'a'] == 0)
    {
        nod->fiu[c[0] - 'a'] = new trie;
    }
    introdu(nod->fiu[c[0] - 'a'], c + 1, ind);
}

int main()
{
    int n, i;
    T = new trie;
    fin >> a;
    fin >> n;
    for(i = 1 ; i <= n ; i++)
    {
        fin >> b;
        introdu(T, b, i);
    }
    st = dr = 0;
    Q[st] = T;
    T->fail = T;
    while(st <= dr)
    {
        trie *nod = Q[st];
        st++;
        for(i = 0 ; i < 26 ; i++)
        {
            if(nod->fiu[i])
            {
                Q[++dr] = nod->fiu[i];
                trie *son = nod->fiu[i];
                son->fail = nod->fail;
                while(son != T && son->fail->fiu[i] == 0)
                    son->fail = son->fail->fail;
                if(son->fail->fiu[i] && son->fail->fiu[i] != son)
                    son->fail = son->fail->fiu[i];
            }
        }
    }
    trie *nod = T;
    for(i = 0 ; a[i] ; i++)
    {
        while(nod != T && nod->fiu[a[i] - 'a'] == 0)
            nod = nod->fail;
        if(nod->fiu[a[i] - 'a'])
            nod = nod->fiu[a[i] - 'a'];
        nod->nr++;
    }
    for(i = dr ; i >= 1 ; i--)
    {
        Q[i]->fail->nr += Q[i]->nr;
        rez[Q[i]->indice] = Q[i]->nr;
    }
    for(i = 1 ; i <= n ; i++)
    {
        fout << rez[i] << "\n";
    }
}