Cod sursa(job #1689589)

Utilizator george_stelianChichirim George george_stelian Data 14 aprilie 2016 13:11:33
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.78 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

class aho_corasick
{
    public:
        void add_word(char sir[])
        {
            int lim=strlen(sir),nod=rad;
            for(int i=0;i<lim;i++)
            {
                if(v[nod].delta[cod(sir[i])]==nil) v[nod].delta[cod(sir[i])]=newnode();
                nod=v[nod].delta[cod(sir[i])];
            }
            v[nod].words.push_back(cnt++);
        }
        void compute_delta_pi()
        {
            v[rad].pi=rad;
            q.push_back(rad);
            for(int i=0;i<q.size();i++)
            {
                int nod=q[i];
                for(int j=0;j<sigma;j++)
                {
                    int k=v[nod].pi;
                    while(k!=rad && v[k].delta[j]==nil) k=v[k].pi;
                    if(k!=nod && v[k].delta[j]!=nil) k=v[k].delta[j];
                    if(v[nod].delta[j]==nil) v[nod].delta[j]=k;
                    else
                    {
                        v[v[nod].delta[j]].pi=k;
                        q.push_back(v[nod].delta[j]);
                    }
                }
            }
            reverse(q.begin(),q.end());
        }
        vector<int> get_freq(char sir[])
        {
            vector<int> freq=vector<int>(cnt,0);
            int lim=strlen(sir),nod=rad;
            for(int i=0;i<lim;i++)
            {
                nod=v[nod].delta[cod(sir[i])];
                v[nod].sum++;
            }
            for(vector<int>::iterator it=q.begin();it!=q.end();it++)
                if(*it!=rad) v[v[*it].pi].sum+=v[*it].sum;
            for(int i=0;i<v.size();i++)
                for(vector<int>::iterator it=v[i].words.begin();it!=v[i].words.end();it++)
                    freq[*it]+=v[i].sum;
            return freq;
        }
    private:
        static const int nil=-1,sigma=26;
        struct node
        {
            int pi,sum;
            vector<int> delta,words;
            node()
            {
                delta=vector<int>(sigma,nil);
                sum=pi=0;
            }
        };
        vector<node> v=vector<node>(1,node());
        vector<int> q;
        int rad=0,cnt=0;

        int cod(char c)
        {
            return c-'a';
        }
        int newnode()
        {
            v.push_back(node());
            return v.size()-1;
        }
}v;
char sir[1000010],sir1[10010];

int main()
{
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
    int n;
    scanf("%s\n%d",sir,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("\n%s",sir1);
        v.add_word(sir1);
    }
    v.compute_delta_pi();
    vector<int> sol=v.get_freq(sir);
    for(int i=0;i<n;i++) printf("%d\n",sol[i]);
}