Cod sursa(job #2344030)

Utilizator refugiatBoni Daniel Stefan refugiat Data 14 februarie 2019 17:55:18
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream si("ahocorasick.in");
ofstream so("ahocorasick.out");
int sol[105];
string s,c;

struct trie{
    trie *f[26],*fail;
    int val;
    vector<int> poz;
    trie()
    {
        memset(f,0,sizeof(f));
        fail=NULL;
        val=0;
    }
}*t;
void add(int x)
{
    trie *nod=t;
    for(int i=0;i<c.size();++i)
    {
        if(nod->f[c[i]-'a']==NULL)
        {
            nod->f[c[i]-'a']=new trie();
        }
        nod=nod->f[c[i]-'a'];
    }
    nod->poz.push_back(x);
}
vector<trie*> v;
void bfs()
{
    trie *nod;
    v.push_back(t);
    t->fail=t;
    for(int i=0;i<v.size();++i)
    {
        for(int j=0;j<26;++j)
        {
            if(v[i]->f[j]!=NULL)
            {
                nod=v[i]->fail;
                while(nod->f[j]==NULL&&nod!=t)
                {
                    nod=nod->fail;
                }
                if(nod->f[j]!=NULL&&nod->f[j]!=v[i]->f[j])
                {
                    nod=nod->f[j];
                }
                v[i]->f[j]->fail=nod;
                v.push_back(v[i]->f[j]);
            }
        }
    }
}
void bfs2()
{
    for(int i=v.size()-1;i>=0;--i)
    {
        if(v[i]->fail!=NULL)
        {
            v[i]->fail->val+=v[i]->val;
        }
        for(int j=0;j<v[i]->poz.size();++j)
        {
            sol[v[i]->poz[j]]+=v[i]->val;
        }
    }
}
int main()
{
    int n;
    si>>s;
    si>>n;
    t=new trie();
    for(int i=1;i<=n;++i)
    {
        si>>c;
        add(i);
    }
    bfs();
    trie *nod=t;
    for(int i=0;i<s.size();++i)
    {
        while(nod->f[s[i]-'a']==NULL&&nod!=t)
        {
            nod=nod->fail;
        }
        if(nod->f[s[i]-'a']!=NULL)
            nod=nod->f[s[i]-'a'];
        nod->val++;
    }
    bfs2();
    for(int i=1;i<=n;++i)
        so<<sol[i]<<'\n';
    return 0;
}