Johnny07
Savu Ioan-Daniel
• Johnny07
logout | contul meu
infoarena informatica de performanta

    infoarena
    blog
    forum
    calendar
    profilul meu
    mesaje

    Home
    Arhiva de probleme
    Arhiva educatională
    Arhiva monthly
    Arhiva ACM
    Concursuri
    Concursuri virtuale
    Clasament
    Articole
    Downloads
    Links
    Documentaţie
    Despre infoarena
    Monitorul de evaluare
    Trimite soluţii
    Contul meu

! Cautare
In curand...

114755 membri inregistrati
19:06:14

Fii un bun infoarenaut! Implică-te!

Pagini recente » Cod sursa (job #2589064) | Borderou de evaluare (job #2589040) | Cod sursa (job #2589040) | Borderou de evaluare (job #2589056) | Cod sursa (job #2589056)
Cod sursa(job #2589040)
Utilizator 	Johnny07Savu Ioan-Daniel Johnny07 	Data 	25 martie 2020 18:24:37
Problema 	NFA 	Scor 	25
Compilator 	cpp-64 	Status 	done
Runda 	Arhiva de probleme 	Marime 	2.07 kb
Raporteaza aceasta sursa


#include <bits/stdc++.h>

//#include "Automat.cpp"

using namespace std;

ifstream fin("nfa.in");

ofstream fout("nfa.out");



class Automat

{

private:

    int n, m;

    int nod_init;

    bool is_final[310];

    bool am_fost[310][160];

    int vec[310];

    vector<int> muchie[310][30];

    int n_final_nodes;

public:

    friend ifstream& operator >> (ifstream&, Automat &);

    bool checkWord(string &);

    inline void setMem(int);

};



inline void Automat :: setMem(int siz)

{

    for (int i = 0; i<= n; i++)

        for (int j = 0; j <= siz + 1; j++)

            am_fost[i][j] = 0;

}



ifstream& operator >> (ifstream& fin, Automat &obj)

{

    int aux, nods, nodf;

    char c;

    fin >> obj.n >> obj.m >> obj.n_final_nodes;

    fin >> obj.nod_init;

    for (int i = 0 ; i <= obj.n; i++)

    {

        obj.is_final[i] = false;

    }

    for (int i = 1; i<= obj.n_final_nodes; i++)

    {

        fin >> aux;

        obj.is_final[aux] = true;

    }

    for (int i = 1; i<= obj.m; i++)

    {

        fin >> nods >> nodf >> c;

        obj.muchie[nods][c - 'a'].push_back(nodf);

    }

    return fin;

}



bool Automat::checkWord(string &s)

{

    queue <int> q_n;

    queue <int> q_l;

    int nod, l;

    int siz = s.size();

    q_n.push(nod_init);

    q_l.push(0);

    while (!q_n.empty())

    {

        nod = q_n.front();

        l = q_l.front();



        q_n.pop();

        q_l.pop();

        if (l == siz)

        {

            if (is_final[nod] == 1) return 1;

        }

        else

        {

            for (auto next : muchie[nod][s[l] - 'a'])

                if (!am_fost[next][l + 1])

                    {
                        am_fost[next][l + 1] = true;

                        q_n.push(next);

                        q_l.push(l + 1);

                    }

        }

    }

    return 0;

}





int main()

{

    Automat aut;

    fin >> aut;

    string s;

    int n;

    fin >> n;

    for (int i = 1 ; i <= n; i++)

    {

        fin >> s;

        aut.setMem(s.size());

        fout << aut.checkWord(s) <<"\n";

    }



    return 0;



}

    © 2004-2020 Asociatia infoarena
    Prima pagina
    Despre infoarena
    Termeni si conditii
    Contact
    Sari la inceputul paginii ↑

Creative Commons License
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena
este publicat sub licenta Creative Commons Attribution-NonCommercial 2.5.