Cod sursa(job #1235074)

Utilizator sebinechitasebi nechita sebinechita Data 28 septembrie 2014 18:34:55
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
#define alpha 26
struct ac{
    vector<int> v;
    int val;
    ac *fiu[alpha], *fail;
    ac(){
        val=0;
        memset(fiu, 0, sizeof(fiu));
        fail=0;
    }
}*q[1000002];

ac *t;

void ins(ac *nod, char* s, int i)
{
    if(!s[0])
    {
        nod->v.push_back(i);
        return;
    }
    int son=s[0]-'a';
    if(!nod->fiu[son])
        nod->fiu[son]= new ac;
    ins(nod->fiu[son], s+1, i);
}
int st, dr;
void bfs()
{
    ac *fail;
    st=dr=1;
    t->fail=t;
    q[1]=t;
    while(st<=dr)
    {
        ac *nod=q[st];
        st++;
        for(int i=0;i<26;i++)
        {
            if(!nod->fiu[i])
                continue;
            fail=nod->fail;
            while(fail!=t && !fail->fiu[i])
                fail=fail->fail;
            if(fail->fiu[i] && fail->fiu[i]!=nod->fiu[i])
                fail=fail->fiu[i];
            nod->fiu[i]->fail=fail;
            q[++dr]=nod->fiu[i];
        }
    }
    t->fail=0;
}
char a[1000002];
char b[10002];
void compute()
{
    int i;
    ac* nod=t;
    for(i=0;a[i];i++)
    {

        while(nod!=t && !nod->fiu[a[i]-'a'])
        {
            nod=nod->fail;
        }
        if(nod->fiu[a[i]-'a'])
            nod=nod->fiu[a[i]-'a'];
        nod->val++;
    }
}

int rez[102];

void antibfs()
{
    for(int i=dr;i>0;i--)
    {
        ac *nod=q[i];
        if(q[i]->fail)
            q[i]->fail->val+=q[i]->val;
        for(vector<int> :: iterator it=nod->v.begin();it!=nod->v.end();it++)
        {
            rez[*it]=q[i]->val;
        }
    }
}


int main()
{
    int m, i;
    t=new ac;
    fin >> a;
    fin >> m;
    for(i=1; i<=m; i++)
    {
        fin>>b;
        ins(t, b, i);
    }
    bfs();

    compute();
    //return 0;
    antibfs();
    for(i=1;i<=m;i++)
    {
        fout<<rez[i]<<"\n";
    }
}