Cod sursa(job #2031495)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 3 octombrie 2017 11:40:10
Problema Aho-Corasick Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>
#define Nmax 101
using namespace std;

int n,rez[Nmax];
string S,c;

struct trie{
    trie *f[26],*fail;
    vector<int> P;
    int val;
    trie()
    {
        val = 0;
        memset(f,0,sizeof(f));
        fail = NULL;
    }
}*T;
vector<trie*> C;

void add(int poz)
{
    trie *nod = T;
    char it;
    for (int i=0;i<c.size();i++)
    {
        it = c[i];
        if (nod->f[it-'a']==NULL)
            nod->f[it-'a'] = new trie();
        nod = nod->f[it-'a'];
    }
    nod->P.push_back(poz);
}

void bfs()
{
    C.push_back(T);
    T->fail = T;
    for (int k=0;k<C.size();k++)
    {
        trie *it = C[k];
        for (int i=0;i<26;i++)
            if (it->f[i]!=NULL)
            {
                trie *nod = it->fail;
                while (nod->f[i]==NULL && nod!=T)
                    nod = nod->fail;
                if (nod->f[i]!=NULL && nod->f[i]!=it->f[i])
                    nod = nod->f[i];
                it->f[i]->fail = nod;
                C.push_back(it->f[i]);
            }
    }
}

void bfs2()
{
    for (int i=C.size()-1;i>=0;i--)
    {
        C[i]->fail->val += C[i]->val;
        for (int j=0;j<C[i]->P.size();j++)
            rez[C[i]->P[j]] += C[i]->val;
    }
}

int main()
{
    freopen("ahocorasick.in","r",stdin);
    freopen("ahocorasick.out","w",stdout);
    T = new trie();
    cin>>S;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>c;
        add(i);
    }

    bfs();

    trie *nod = T;
    char it;
    for (int i=0;i<S.size();i++)
    {
        it = S[i];
        while (nod->f[it-'a']==NULL && nod!=T)
            nod = nod->fail;
        if (nod->f[it-'a']!=NULL)
            nod = nod->f[it-'a'];
        nod->val++;
    }

    bfs2();

    for (int i=1;i<=n;i++)
        cout<<rez[i]<<'\n';

    return 0;
}