Cod sursa(job #1236019)

Utilizator thewildnathNathan Wildenberg thewildnath Data 1 octombrie 2014 09:34:24
Problema Aho-Corasick Scor 75
Compilator cpp Status done
Runda Arhiva educationala Marime 3.07 kb
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<string>

using namespace std;

#define NMAX 102


int n;
int sol[NMAX];

string cuv, text;

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

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

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

        letter=Letter;
    }
};

class aho_corasick_automaton
{
private:
    vector<state> states;

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

        return states.size()-1;
    }

public:
    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(int nod)
    {
        if(states[nod].father)
        {
            if(!states[states[nod].father].solved)
                build_fails(states[nod].father);

            int k=states[states[nod].father].fail;

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

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

            states[nod].fail=k;
        }

        states[nod].solved=true;

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

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

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

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

            for(int aux=k; aux; aux=states[aux].fail)
            {
                for(int j=0; j<states[aux].word.size(); ++j)
                    ++sol[states[aux].word[j]];
            }
        }
    }
};

aho_corasick_automaton automaton;

int main()
{
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);

    cin>>text;

    scanf("%d\n", &n);
    for(int i=1; i<=n; ++i)
    {
        cin>>cuv;

        automaton.add_word(cuv, i);
    }

    automaton.build_fails(0);

    automaton.run_automaton(text);

    for(int i=1; i<=n; ++i)
        printf("%d\n", sol[i]);

    return 0;
}