Cod sursa(job #1251487)

Utilizator misinozzz zzz misino Data 29 octombrie 2014 16:38:30
Problema Aho-Corasick Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include<fstream>
#include<cstring>
#include<vector>

#define N 100100
#define M 10010

using namespace std;

ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");

int i,n,j,sol[N];

char s[N],s1[M];

struct aho{
    vector<int>v;
    aho *fii[26],*fail;
    int nr;

    aho(){
        fail = NULL;
        nr = 0;
        memset(fii, NULL, sizeof(fii));
    }
};

aho *t,*nod,*nod2;
vector<aho*>q;

inline void insert(char *p, int poz){
    nod = t;

    while(*p)
    {
        if(!nod -> fii[*p - 'a'])
            nod -> fii[*p - 'a'] = new aho;

        nod = nod -> fii[*p - 'a'];
        ++p;
    }

    nod -> v.push_back(poz);
}

inline void Bfs(){
    t -> fail = t;

    q.push_back(t);

    for(i = 0; i < q.size(); ++i)
    {
        nod = q[i];

        for(j = 0; j <= 25; ++j)
            if(nod -> fii[j])
            {
                nod2 = nod -> fail;

                while(nod2 != t && !nod2 -> fii[j])
                    nod2 = nod2 -> fail;

                if(nod2 -> fii[j] && nod2 -> fii[j] != nod -> fii[j])
                    nod2 = nod2 -> fii[j];

                nod -> fii[j] -> fail = nod2;
                q.push_back(nod -> fii[j]);
            }
    }

    t -> fail = NULL;
}

inline void AntiBfs(){
    for(i = q.size() - 1; i; --i)
    {
        nod = q[i];

        nod -> fail -> nr += nod -> nr;

        for(vector<int>::iterator it = nod -> v.begin(); it != nod -> v.end(); ++it)
            sol[*it] = nod -> nr;
    }
}

int main()
{
    t = new aho;

    f >> (s + 1) >> n;

    for(i = 1; i <= n; ++i)
    {
        f >> s1;

        insert(s1, i);
    }

    Bfs();

    nod = t;

    for(i = 1; s[i]; ++i)
    {
        while(nod != t && !nod -> fii[s[i] - 'a'])
            nod = nod -> fail;

        if(nod -> fii[s[i] - 'a'])
            nod = nod -> fii[s[i] - 'a'];

        ++nod -> nr;
    }

    AntiBfs();

    for(i = 1; i <= n; ++i)
        g << sol[i] << '\n';

    return 0;
}