Cod sursa(job #2396947)

Utilizator cc4infinityCojocaru Catalin cc4infinity Data 3 aprilie 2019 23:08:31
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");

int sf[10005],i,j,x,y,a,b,m,n,poz;
string s,s1;

struct trie
{
    vector<int> sf;
    int np;
    trie *cp[26],*f;
    trie()
    {
        //sf=0;
        np=0;
        f=NULL;
        for (int i=0;i<26;i++)
            cp[i]=NULL;
    }
};
trie *root=new trie;
trie *bfs[1000003];

void ins()
{
    int l=s1.size();
    trie *nod=root;
    for (int j=0;j<l;j++)
        {
            int ch=s1[j]-'a';
            if (nod->cp[ch]==NULL)
                nod->cp[ch]=new trie;
            nod=nod->cp[ch];
        }
    nod->sf.push_back(i);
}

int main()
{

    fin>>s;
    fin>>n;
    for (i=1;i<=n;i++)
    {
        fin>>s1;
        ins();
    }
    root->f=root;
    bfs[0]=root;
    //queue<trie> q;
    int p=1,u=0;
    bfs[1]=root;
    for (i=0;i<26;i++)
        if (root->cp[i]) {root->cp[i]->f=root; bfs[++u]=root->cp[i];}// pe nivelu 1 toate au fail-u in root
             else root->cp[i]=root; // pentru cvazu can fail-u tre sa duca in root
    while (p<=u)
    {
        trie *nod=bfs[p];
        for (i=0;i<26;i++)
          if (nod->cp[i] && nod->cp[i]!=root)
          {
              trie *fl=nod->f;
              while (fl!=root && fl->cp[i]==NULL)
                fl=fl->f;
              fl=fl->cp[i];
              nod->cp[i]->f=fl;

              bfs[++u]=nod->cp[i];
              //if (nod->cp[i]!=fl)
              //for (int j=0;j<fl->sf.size();j++)
               // nod->cp[i]->sf.push_back(fl->sf[j]);
          }
        p++;
    }

    // fac cu potriviri, tipa invers parcurg, si arat de cate ori so potrivit inca din primu bfs
    // si adun numaru de potriviri de la fiecare nod si la fail-u lui,ca tipa e acelasi, si la sfarsit adaug numaru de potrivirai la sfarsit de cuvint, tabelu cu sol
    int l=s.size();
    trie *nod=root;
    for (i=0;i<l;i++)
    {
        int ch=s[i]-'a';
        while (nod!=root && nod->cp[ch]==NULL)
            nod=nod->f;
        nod=nod->cp[ch];
        nod->np++;
        //for (int j=0;j<nod->sf.size();j++) sf[nod->sf[j]]++; SCOT!!
    }
    for (i=u;i>0;i--)
    {
         if (bfs[i]->f!=root) bfs[i]->f->np+=bfs[i]->np;
         for (int j=0;j<bfs[i]->sf.size();j++)
            sf[bfs[i]->sf[j]]=bfs[i]->np;
    }
    for (i=1;i<=n;i++)
        fout<<sf[i]<<"\n";
    return 0;
}