Cod sursa(job #1225712)

Utilizator alecsandrualex cuturela alecsandru Data 3 septembrie 2014 14:16:14
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.08 kb
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

char s[1000001],m[101][10001];
int rez[101],r[101];

class Ahocorasick
{
public:
    struct Nod
    {
        Nod *advance[26],*euro,*dolar;
        int ind;
        Nod()
        {
            int i;
            for(i=0;i<=25;i++)
                advance[i]=0;
            euro=0;
            dolar=0;
            ind=0;
        }
    };

    Nod *alpha;

    Ahocorasick()
    {
        alpha=new Nod;
    }

    void add(char *s,int ind)
    {
        int i;
        Nod *poz;
        poz=alpha;
        for(i=0;s[i];i++)
        {
            if(poz->advance[s[i]-'a']==0)
                poz->advance[s[i]-'a']=new Nod;
            poz=poz->advance[s[i]-'a'];
        }
        poz->ind=ind;
    }

    void dolar_euro()
    {
        queue <Nod*> q;
        int i;
        Nod *tata,*temp;
        alpha->dolar=0;
        alpha->euro=alpha;
        for(i=0;i<26;i++)
            if(alpha->advance[i]!=NULL)
            {
                alpha->advance[i]->dolar=alpha;
                q.push(alpha->advance[i]);
            }
        while(!q.empty())
        {
            tata=q.front();
            q.pop();
            for(i=0;i<26;i++)
                if(tata->advance[i]!=NULL)
                {
                    temp=tata;
                    while(temp->dolar!=NULL&&temp->dolar->advance[i]==NULL)
                        temp=temp->dolar;
                    if(temp->dolar==NULL)
                        tata->advance[i]->dolar=alpha;
                    else
                        tata->advance[i]->dolar=temp->dolar->advance[i];
                    q.push(tata->advance[i]);
                }
            if(tata->dolar->ind!=0)
                tata->euro=tata->dolar;
            else
                tata->euro=tata->dolar->euro;
        }
    }
};

Ahocorasick A;

int main()
{
    int n,i,nn,cnt,j;
    char temp[10001];
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    gets(s);
    scanf("%d\n",&n);
    nn=0;
    for(i=1;i<=n;i++)
    {
        gets(temp);
        cnt=1;
        for(j=1;j<=nn;j++)
            if(strcmp(m[j],temp)==0)
            {
                cnt=0;
                r[i]=j;
                break;
            }
        if(cnt==1)
        {
            strcpy(m[++nn],temp);
            r[i]=nn;
            A.add(temp,nn);
        }
    }
    A.dolar_euro();
    Ahocorasick::Nod *poz,*euro;

    poz=A.alpha;

    for(i=0;s[i]!=0;i++)
    {
        while(poz->dolar!=NULL&&poz->advance[s[i]-'a']==NULL)
        {
            poz=poz->dolar;
        }
        if (poz->advance[s[i]-'a']!=NULL)
            poz=poz->advance[s[i]-'a'];
        if(poz->ind!=0)
        {
            rez[poz->ind]++;
        }
        euro=poz->euro;
        while(euro!=A.alpha)
        {
            rez[euro->ind]++;
            euro=euro->euro;
        }
    }
    for(i=1;i<=n;i++)
    {
        printf("%d\n",rez[r[i]]);
    }
    return 0;
}