Cod sursa(job #1100741)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 7 februarie 2014 13:51:24
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

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

const int Nmax = 110;
const int Amax = 26;
const int Smax = 1e6 + 100;
const int Cmax = 1e4 + 100;

struct AC{
    vector <int> End;
    AC *F[Amax], *fail;
    int nr;
    AC()
    {
        fail = 0; nr = 0;
        memset(F, 0, sizeof F);
    }
};

int N, st, dr, SOL[Nmax];
char A[Smax], C[Cmax];
AC *Q[Cmax * Cmax], *T;

void Insert(AC *nod, char *p, int i)
{
    if(*p == NULL)
    {
        nod -> End.push_back(i);
        return;
    }
    int next = *p - 'a';
    if(!nod -> F[next]) nod -> F[next] = new AC;
    Insert(nod -> F[next], p + 1, i);
}

void BFS()
{
    T->fail = T;
    AC *fpoz;
    Q[1] = T;
    for(st = dr = 1; st <= dr; st++)
    {
        AC *nod = Q[st];
        for(int i = 0; i < Amax; i++)
            if(nod->F[i] != NULL)
            {
                for(fpoz = nod->fail; fpoz != T && fpoz->F[i] == NULL; fpoz = fpoz->fail);

                if(fpoz->F[i] != NULL & fpoz->F[i] != nod->F[i]) fpoz = fpoz->F[i];
                nod->F[i]->fail = fpoz;
                Q[++dr] = nod->F[i];
            }
    }
    T->fail = NULL;
}

void REV_BFS()
{
    for(; dr > 0; dr--)
    {
        AC *nod = Q[dr];
        if(nod->fail != NULL)
            nod->fail->nr += nod->nr;
        for(int i = 0; i < nod->End.size(); i++)
            SOL[nod->End[i]] = nod->nr;
    }
}

int main()
{
    fin.getline(A + 1, Smax);

    fin >> N; T = new AC; fin.get();
    for(int i = 1; i <= N; i++)
    {
        fin.getline(C + 1, Cmax);
        Insert(T, C + 1, i);
    }

    BFS();
    int M = strlen(A + 1); AC *nod = T;
    for(int i = 1; i <= M; i++)
    {
        int next = A[i] - 'a';
        for(; nod != T && nod->F[next] == NULL; nod = nod->fail);
        if(nod->F[next] != NULL) nod = nod->F[next];
        ++nod->nr;
    }

    REV_BFS();
    for(int i = 1; i <= N; i++)
        fout << SOL[i] << '\n';
    return 0;
}