Cod sursa(job #1244984)

Utilizator thewildnathNathan Wildenberg thewildnath Data 18 octombrie 2014 14:56:36
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4 kb
#include<fstream>
#include<iostream>
#include<string.h>
#include<vector>
#include<string>
#include<queue>

using namespace std;

#define NMAX 102


int n;
int sol[NMAX];

string cuv, text;

struct state
{
    bool solved;
    int father, fail;
    int transitions[26];
    int grad, sum;
    char letter;
    vector<int> word;

    state(int Father=0, char Letter=0)
    {
        solved=false;
        fail=0;
        father=Father;
        grad=0;
        sum=0;

        memset(transitions, 0, sizeof(transitions));

        letter=Letter;
    }
};

class aho_corasick_automaton
{
public:
    vector<state> states;

    inline int new_automaton_state(int father=0, char letter=0)
    {
        states.push_back(state(father, letter));

        return states.size()-1;
    }

    aho_corasick_automaton()
    {
        new_automaton_state();
    }

    inline void add_word(const string &s, int cuv_num)
    {
        int k=0, poz;

        for(int i=0; i<s.size(); ++i)
        {
            poz=s[i]-'a';

            if(!states[k].transitions[poz])
            {
                int x=new_automaton_state(k, s[i]-'a');
                states[k].transitions[poz]=x;
            }
            k=states[k].transitions[poz];
        }

        states[k].word.push_back(cuv_num);
    }

    inline void build_fails()
    {
        queue<int> q;
        int nod, k;

        q.push(0);

        while(!q.empty())
        {
            nod=q.front();
            q.pop();

            if(states[nod].father)
            {
                k=states[states[nod].father].fail;

                while(k && !states[k].transitions[states[nod].letter])
                    k=states[k].fail;

                if(states[k].transitions[states[nod].letter])
                    k=states[k].transitions[states[nod].letter];

                states[nod].fail=k;
                ++states[states[nod].father].grad;
                ++states[states[nod].fail].grad;
            }

            states[nod].solved=true;

            for(int i=0; i<26; ++i)
                if(states[nod].transitions[i] && !states[states[nod].transitions[i]].solved)
                    q.push(states[nod].transitions[i]);
        }
    }

    void fin()
    {
        queue<int> q;
        int nod;

        for(int i=0; i<states.size(); ++i)
            if(!states[i].grad)
                q.push(i);

        while(!q.empty())
        {
            nod=q.front();
            q.pop();

            states[states[nod].fail].sum+=states[nod].sum;
            --states[states[nod].father].grad;
            --states[states[nod].fail].grad;

            if(states[nod].father && !states[states[nod].father].grad)
                q.push(states[nod].father);

            if(states[nod].fail!=states[nod].father && states[nod].father && !states[states[nod].fail].grad)
                q.push(states[nod].fail);
        }
    }

    inline int run_automaton(const string &s)
    {
        int nod=0, aux;

        for(int i=0; i<s.size(); ++i)
        {
            while(nod && !states[nod].transitions[s[i]-'a'])
                nod=states[nod].fail;

            if(states[nod].transitions[s[i]-'a'])
                nod=states[nod].transitions[s[i]-'a'];

            ++states[nod].sum;
        }
    }
};

aho_corasick_automaton automaton;

int main()
{
    ifstream cin("ahocorasick.in");
    ofstream cout("ahocorasick.out");

    ios_base::sync_with_stdio(false);

    cin>>text;

    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>cuv;

        automaton.add_word(cuv, i);
    }

    automaton.build_fails();

    automaton.run_automaton(text);

    automaton.fin();

    for(int i=0; i<automaton.states.size(); ++i)
    {
        for(int j=0;j<automaton.states[i].word.size(); ++j)
            sol[automaton.states[i].word[j]]=automaton.states[i].sum;
    }

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

    return 0;
}