Cod sursa(job #2919954)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 20 august 2022 20:26:16
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.75 kb
#include <bits/stdc++.h>
#include <sys/time.h>
#define MAXLG 1000000
/// TONI BO$$ was here
/// #MLC

using namespace std;

vector <string> arr;

struct trie
{
    int _goto[26], fail;
    vector <int> occ;
    trie ()
    {
        memset(_goto, 0, sizeof(_goto));
        fail = 0;
    }
};

vector <trie *> automaton;

int nostates;
int res[101];
int matches[MAXLG + 1];

int main()
{
    int n, i, j, curstate;
    string s;
    string aux;
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
    //trie X;
    automaton.push_back(new trie);
    cin >> s;
    cin >> n;
     struct timeval start, stop, elapsed;
    //gettimeofday(&start, NULL);
    getline(cin, aux);
    for(i = 0; i < n; i++)
    {

        getline(cin, aux);
        arr.push_back(aux);
    }
    /*gettimeofday(&stop, &start);
    //timersub(&stop, &start, &elapsed);
    printf("Busy loop took %lu.%06lu seconds\n", start.tv_sec,
            start.tv_usec);
    printf("Busy loop took %lu.%06lu seconds\n", stop.tv_sec,
            stop.tv_usec);*/
    nostates = 1;
    curstate = 0;

    //gettimeofday(&start, NULL);
    for(i = 0; i < n; i++)
    {
        string &word = arr[i];
        curstate = 0;
        for(j = 0; j < word.size(); j++)
        {
            trie * &aux = automaton[curstate];
            if(aux->_goto[word[j] - 'a'])
                curstate = aux->_goto[word[j] - 'a'];
            else
            {
                curstate = nostates, aux->_goto[word[j] - 'a'] = nostates++;
                automaton.push_back(new trie);
            }
        }
        automaton[curstate]->occ.push_back(i);
    }

    queue < int > q;
    for(i = 0; i < 26; i++)
        if(automaton[0]->_goto[i])
            q.push(automaton[0]->_goto[i]);
    /*
    */
    while(!q.empty())
    {
        int state = q.front();
        q.pop();
        /// for(i<-0,26)...
        for(int ch = 0; ch < 26; ch++)
            if(automaton[state]->_goto[ch])
            {
                int pi = automaton[state]->fail;
                while(pi && !automaton[pi]->_goto[ch])
                    pi = automaton[pi]->fail;
                if(automaton[pi]->_goto[ch])
                {
                    automaton[automaton[state]->_goto[ch]]->fail = automaton[pi]->_goto[ch];
                    vector <int> &aux = automaton[automaton[pi]->_goto[ch]]->occ;
                    vector <int> &dest = automaton[automaton[state]->_goto[ch]]->occ;
                    int z = aux.size();
                    for(int i = 0; i < z; i++)
                        dest.push_back(aux[i]);
                }
                q.push(automaton[state]->_goto[ch]);
            }
    }

    curstate = 0;
    int m = s.size(), z;
    char it;
    //gettimeofday(&start, NULL);
    for(int i = 0; i < m; i++)
    {
        it = s[i];
        while(curstate && !automaton[curstate]->_goto[it - 'a'])
            curstate = automaton[curstate]->fail;
        if(automaton[curstate]->_goto[it - 'a'])
            curstate = automaton[curstate]->_goto[it - 'a'];
        matches[curstate]++;
    }
    /*gettimeofday(&stop, &start);
    //timersub(&stop, &start, &elapsed);
    printf("Busy loop took %lu.%06lu seconds\n", start.tv_sec,
            start.tv_usec);
    printf("Busy loop took %lu.%06lu seconds\n", stop.tv_sec,
            stop.tv_usec);*/
    for(int i = 0; i < nostates; i++)
        //if(matches[i])
        {
            int k = matches[i];
            vector <int> &aux = automaton[i]->occ;
            z = aux.size();
            for(int j = 0; j < z; j++)
                res[aux[j]] += k;
        }
    for(i = 0; i < n; i++)
        printf("%d\n", res[i]);

    return 0;
}