Cod sursa(job #1690618)

Utilizator sebinechitasebi nechita sebinechita Data 15 aprilie 2016 13:20:13
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
#define MAX 1000010

char c[MAX], c2[10010];

struct node{
    int val = 0;
    vector <int> v;
    node *fiu[26] = {0}, *fail = 0;
} *R, *Q[MAX];

void introdu(node *R, char c[], int i)
{
    if(c[0] == 0)
    {
        R->v.push_back(i);
        return;
    }
    if(R->fiu[c[0] - 'a'] == 0)
    {
        R->fiu[c[0] - 'a'] = new node;
    }
    introdu(R->fiu[c[0] - 'a'], c + 1, i);
}

int st, dr, rez[103];

void bfs()
{
    st = 1;
    dr = 0;
    Q[++dr] = R;
    R->fail = R;
    while(dr - st + 1)
    {
        node* nod = Q[st++];
        for(int i = 0 ; i < 26 ; i++)
        {
            node *son = nod->fiu[i];
            if(son)
            {
                Q[++dr] = son;
                son->fail = nod->fail;
                while(son->fail != R && son->fail->fiu[i] == 0)
                    son->fail = son->fail->fail;
                if(son->fail->fiu[i] && son != son->fail->fiu[i])
                    son->fail = son->fail->fiu[i];
            }
        }
       // cout << nod << " " << nod->fail << "\n";
    }
}

int main()
{
    R = new node;
    int n, i;
    fin >> c;
    fin >> n;
    for(i = 1 ; i <= n ; i++)
    {
        fin >> c2;
        introdu(R, c2, i);
    }
    bfs();
    node *nod = R;
    for(i = 0 ; c[i] ; i++)
    {
        while(nod != R && nod->fiu[c[i] - 'a'] == 0)
        {
            nod = nod->fail;
        }
        if(nod->fiu[c[i] - 'a'])
            nod = nod->fiu[c[i] - 'a'];
        nod->val++;
    }
    //cout << "\n";
    for(i = dr ; i >= 1 ; i--)
    {

        nod = Q[i];
        nod->fail->val += nod->val;
       // cout << nod << " " << nod->val << "\n";
        for(int j = 0 ; j < nod->v.size() ; j++)
        {
            rez[nod->v[j]] = nod->val;
        }
    }
    for(i = 1 ; i <= n ; i++)
    {
        fout << rez[i] << "\n";
    }

    return 0;
}