Cod sursa(job #2384298)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 20 martie 2019 16:46:49
Problema Aho-Corasick Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.89 kb
#include <bits/stdc++.h>
#define SIGMA 26
#define Nmax 105

using namespace std;

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

string A,v[Nmax];
int ans[Nmax];
int N;

class Aho_corasick{

private:

    struct node{

        list <int> pos_words;
        node *fail_node=nullptr;
        node *children[SIGMA];
        node *parent=nullptr;

        node(){

            memset(children,0,sizeof(children));
        }
    };

    node *root=new node;

public:

    void add(const string &s, const int &pos){

        node *current_node=root;
        for(const auto &it:s)
            if(current_node->children[it-'a']){

                current_node->children[it-'a']->parent=current_node;
                current_node=current_node->children[it-'a'];
            }
            else{

                current_node->children[it-'a']=new node;
                current_node->children[it-'a']->parent=current_node;
                current_node=current_node->children[it-'a'];
            }
        current_node->pos_words.push_back(pos);
    }

    void add_fail_nodes(const int &N){

        queue <node*> q;
        node *current_node,*fail_current_node;

        q.push(root);

        while(!q.empty()){

            current_node=q.front();
            q.pop();

            for(int i=0;i<SIGMA;i++)
                if(current_node->children[i]){

                    fail_current_node=current_node->fail_node;

                    while(fail_current_node and !fail_current_node->children[i])
                        fail_current_node=fail_current_node->parent;

                    if(!fail_current_node)
                        current_node->children[i]->fail_node=root;
                    else
                        current_node->children[i]->fail_node=fail_current_node->children[i];

                    for(const auto &it:current_node->children[i]->fail_node->pos_words)
                        current_node->children[i]->pos_words.push_back(it);

                    q.push(current_node->children[i]);
                }
        }
    }

    void query(const string &s, const int &N){

        node *current_node=root;

        for(const auto &it:s){

            while(current_node and !current_node->children[it-'a'])
                current_node=current_node->fail_node;

            if(!current_node)
                current_node=root;
            else{

                current_node=current_node->children[it-'a'];
                for(const auto &it:current_node->pos_words)
                        ++ans[it];
            }
        }
    }
};

int main(){

    f>>A;
    int N;
    f>>N;

    Aho_corasick T;

    for(int i=1;i<=N;i++){

        f>>v[i];
        T.add(v[i],i);
    }

    T.add_fail_nodes(N);

    T.query(A,N);

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

    return 0;
}