Cod sursa(job #1650358)

Utilizator george_stelianChichirim George george_stelian Data 11 martie 2016 17:55:23
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.84 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

class Aho_Corasick
{
    public:
        void add_word(char sir[])
        {
            int n=strlen(sir),nod=rad;
            wordcnt++;
            for(int i=0;i<n;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].indcuv.push_back(wordcnt-1);
        }
        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(v[k].delta[j]!=nil && k!=nod) k=v[k].delta[j];
                    if(v[nod].delta[j]!=nil)
                    {
                        v[v[nod].delta[j]].pi=k;
                        q.push_back(v[nod].delta[j]);
                    }
                    else v[nod].delta[j]=k;
                }
            }
            reverse(q.begin(),q.end());
        }
        vector<int> getfreq(char sir[])
        {
            vector<int> freq=vector<int>(wordcnt,0);
            int n=strlen(sir),nod=rad;
            for(int i=0;i<n;i++)
            {
                nod=v[nod].delta[cod(sir[i])];
                v[nod].nr++;
            }
            for(vector<int>::iterator it=q.begin();it!=q.end();it++)
                if(*it!=rad) v[v[*it].pi].nr+=v[*it].nr;
            for(int i=0;i<v.size();i++)
                for(vector<int>::iterator it=v[i].indcuv.begin();it!=v[i].indcuv.end();it++) freq[*it]=v[i].nr;
            return freq;
        }
    private:
        static const int sigma=26,nil=-1;
        struct node
        {
            int nr,pi;
            vector<int> delta,indcuv;
            node()
            {
                nr=pi=0;
                delta=vector<int>(sigma,nil);
                indcuv=vector<int>();
            }
        };
        vector<node> v=vector<node>(1,node());
        vector<int> q;
        int rad=0,wordcnt=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.getfreq(sir);
    for(int i=0;i<n;i++) printf("%d\n",sol[i]);
    return 0;
}