Cod sursa(job #2919933)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 20 august 2022 19:08:32
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 kb
#include <bits/stdc++.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 f[26];

int main()
{
    int n, i, j, curstate;
    string s;
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
    //trie X;
    automaton.push_back(new trie);
    cin >> s;
    cin >> n;
    for(i = 0; i < n; i++)
    {
        string aux;
        cin >> aux;
        arr.push_back(aux);
    }
    nostates = 1;
    curstate = 0;
    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];
                    for(auto it : automaton[automaton[pi]->_goto[ch]]->occ)
                        automaton[automaton[state]->_goto[ch]]->occ.push_back(it);
                }
                q.push(automaton[state]->_goto[ch]);
            }
    }
    curstate = 0;
    for(auto it : s)
    {
        while(curstate && !automaton[curstate]->_goto[it - 'a'])
            curstate = automaton[curstate]->fail;
        if(automaton[curstate]->_goto[it - 'a'])
            curstate = automaton[curstate]->_goto[it - 'a'];
        vector <int> &aux = automaton[curstate]->occ;
        int z = aux.size();
        for(int i = 0; i < z; i++)
            res[aux[i]]++;
    }
    for(i = 0; i < n; i++)
        printf("%d\n", res[i]);

    return 0;
}