Cod sursa(job #2919871)

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

using namespace std;

vector <string> arr;

map <int,int> _goto[MAXLG + 1];
int fail[MAXLG + 1];
map <int,int> occ[MAXLG + 1];
int nostates;
int res[101];

int main()
{
    int n, i, j, curstate;
    string s;
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
    cin >> s;
    cin >> n;
    for(i = 0; i < n; i++)
    {
        string aux;
        cin >> aux;
        arr.push_back(aux);
    }
    nostates = 1;
    for(i = 0; i < n; i++)
    {
        string &word = arr[i];
        int curstate = 0;
        for(j = 0; j < word.size(); j++)
        {
            map <int,int> &aux = _goto[curstate];
            if(aux[word[j] - 'a'])
                curstate = aux[word[j] - 'a'];
            else
                aux[word[j] - 'a'] = nostates++, curstate = aux[word[j] - 'a'];
        }
        occ[curstate][i] = 1;
    }
    queue < int > q;
    for(i = 1; i < curstate; i++)
        fail[i] = -1;
    for(i = 0; i < 26; i++)
        if(_goto[0][i])
        {
            q.push(_goto[0][i]);
            fail[_goto[0][i]] = 0;
        }
    while(!q.empty())
    {
        int state = q.front();
        q.pop();
        /// for(i<-0,26)...
        for(int ch = 0; ch < 26; ch++)
            if(_goto[state][ch])
            {
                int pi = fail[state];
                while(pi && !_goto[pi][ch])
                    pi = fail[pi];
                if(_goto[pi][ch])
                {
                    fail[_goto[state][ch]] = _goto[pi][ch];
                    map < int, int > &mymap = occ[_goto[pi][ch]];
                    for(map < int, int > :: iterator it = mymap.begin(); it != mymap.end(); ++it)
                        occ[_goto[state][ch]][it -> first] += it -> second;
                }
                else
                    fail[_goto[state][ch]] = 0;
                q.push(_goto[state][ch]);
            }
    }
    curstate = 0;
    for(auto it : s)
    {
        while(curstate && !_goto[curstate][it - 'a'])
            curstate = fail[curstate];
        if(_goto[curstate][it - 'a'])
            curstate = _goto[curstate][it - 'a'];
        map < int, int > &mymap = occ[curstate];
        for(map < int, int > :: iterator it = mymap.begin(); it != mymap.end(); ++it)
            res[it -> first] += it -> second;
    }
    for(i = 0; i < n; i++)
        printf("%d\n", res[i]);

    return 0;
}