Cod sursa(job #2919901)

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

using namespace std;

vector <string> arr;

struct trie
{
    int _goto[26], occ[100], fail;
    trie ()
    {
        for(int i = 0; i < 26; i++)
            _goto[i] = occ[i] = 0;
        for(int i = 0; i < 100; i++)
            occ[i] = 0;
        fail = 0;
    }
};

vector <trie *> automaton;

int nostates;
int res[101];

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[i] = 1;
    }
    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(int i = 0; i < n; i++)
                        automaton[automaton[state]->_goto[ch]]->occ[i] += automaton[automaton[pi]->_goto[ch]]->occ[i];
                }
                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'];
        for(int i = 0; i < n; i++)
            res[i] += automaton[curstate]->occ[i];
    }
    for(i = 0; i < n; i++)
        printf("%d\n", res[i]);

    return 0;
}