Cod sursa(job #2200251)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 30 aprilie 2018 19:16:38
Problema Aho-Corasick Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
#define Nmax 102
using namespace std;

ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");

int n,ans[Nmax];
string A,c;

struct trie{
    trie *f[26];
    trie *next[26],*link,*T;
    vector<int> cuv;
    int val, lit;

    trie(trie *_T,int _lit){
        memset(f,0,sizeof(f));
        memset(next,0,sizeof(next));
        link = 0;
        cuv.clear();
        val = 0;
        T = _T;
        lit = _lit;
    }
}*Root;

trie *go(trie*,int);

trie* getlink(trie *nod){
    if (nod->link) return nod->link;
    if (nod==Root || nod->T==Root) return nod->link = Root;
    return nod->link = go(getlink(nod->T),nod->lit);
}

trie* go(trie *nod, int c){
    if (nod->next[c]) return nod->next[c];
    if (nod->f[c]) return nod->next[c] = nod->f[c];
    return nod->next[c] = go(getlink(nod),c);
}

void add(string s,int id){
    trie *nod = Root;
    for (auto it : s){
        if (!nod->f[it - 'a']) nod->f[it - 'a'] = new trie(nod, it - 'a');
        nod  = nod->f[it-'a'];
    }
    nod->cuv.push_back(id);
}

int main()
{
    Root = new trie(0,-2);
    f>>A;
    f>>n;
    for (int i=1;i<=n;i++){
        f>>c;
        add(c,i);
    }

    trie *nod = Root;
    for (auto it : A){
        nod = go(nod,it-'a');
        nod->val++;
    }

    vector<trie*> H;
    H.push_back(Root);
    for (int i=0;i<H.size();i++){
        for (auto it : H[i]->f){
            if (it) H.push_back(it);
        }
    }

    for (int i=H.size()-1;i>=0;i--){
        getlink(H[i])->val += H[i]->val;
        for (auto C : H[i]->cuv) ans[C] += H[i]->val;
    }

    for (int i=1;i<=n;i++){
        g<<ans[i]<<'\n';
    }

    return 0;
}