Cod sursa(job #2137883)

Utilizator horiainfoTurcuman Horia horiainfo Data 21 februarie 2018 08:58:09
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>

using namespace std;

struct node{
    node *next[30], *go[30], *papa, *link = 0;
    int nr = 0, lastC;

    node(node *papa, int lastC){
        this->papa  = papa;
        this->lastC = lastC;
        memset(next, 0, sizeof(next));
        memset(go, 0, sizeof(go));
    }

} *root = new node(0, ' ');

string text;
vector<node*> v;
node* words[102];

node* getLink(node *it);

node* go(node *it, int c){
    if(it->go[c])     return it->go[c];
    if(it->next[c])   return it->go[c] = it->next[c];
    if(!it->papa)     return it;
    return it->go[c] = go(getLink(it), c);
}

node* getLink(node *it){
    if(!it->papa)       return it;
    if(it->link)        return it->link;
    if(!it->papa->papa) return it->link = it->papa;
    return it->link = go(getLink(it->papa), it->lastC);
}

void getNodesOrder(node *it){
    for(auto next : it->next)
        if(next) getNodesOrder(next);
    v.push_back(it);
}

int main(){
   // freopen("ac.in", "r", stdin);

    cin >> text;
    int n;  cin >> n;
    
    for(int i = 1; i <= n; i ++){
        string s;   cin >> s;
        node *it = root;
        for(auto c : s){
            if(! it->next[c - 'a'])   it->next[c - 'a'] = new node(it, c - 'a');
            it = it->next[c - 'a'];
        }
        words[i] = it;
    }

    node *it = root;
    for(auto c : text)
        it = go(it, c - 'a'), it->nr ++;

    v.push_back(root);
    for(int i = 0; i < v.size(); i ++)
        for(int c = 0; c <= 'z' - 'a'; c ++)
            if(v[i]->next[c]) v.push_back(v[i]->next[c]);

    reverse(v.begin(), v.end());
    for(auto it : v){
        node *next = getLink(it);
        next->nr += it->nr;
    }

    for(int i = 1; i <= n; i ++)
        cout << words[i]->nr << '\n';
    cin >> n;
}