== include(page="template/taskheader" task_id="nfa") ==
Se da un NFA (nondeterministic finite automata) format din N stari, M tranzitii K stari finale si Q cuvinte, fiecare tranzitie presupunand o litera mica din alfabetul limbii engleze,
Afisati pentru fiecare cuvant 1 daca automatul il contine si 0, altfel.
Fie un NFA (nondeterministic finite automata) format din $N$ stari, $M$ tranzitii si $K$ stari finale, fiecare tranzitie presupunand o litera mica din alfabetul limbii engleze. Dandu-se $Q$ cuvinte, afisati pentru fiecare $1$ daca automatul il contine si $0$, altfel.
h2. Date de intrare
Fişierul de intrare $nfa.in$ va contine pe prima linie 3 numere N, M si K (cu semnificatia din enunt), iar pe a 2-a linie un numar S, reprezentand starea initiala. Pe a 3-a linie se vor afla K numere reprezentand starile finale. Pe urmatoarele M linii se gasesc cate 2 numere si un caracter reprezentand tranzitia dintre 2 stari. Pe urmatoare linie se va afla un numar Q, urmatoarele Q linii vor contine cate 1 sir de caractere.
Fişierul de intrare $nfa.in$ va contine:
* Pe prima linie 3 numere $N$, $M$ si $K$ (cu semnificatia din enunt).
* Pe a 2-a linie un numar $S$, reprezentand starea initiala.
* Pe a 3-a linie se vor afla $K$ numere reprezentand starile finale.
* Pe urmatoarele $M$ linii se gasesc cate $2$ numere si un caracter reprezentand tranzitia dintre $2$ stari.
* Pe urmatoarea linie se va afla un numar $Q$, urmat de $Q$ linii, fiecare cu cate un sir de caractere.
h2. Date de ieşire
În fişierul de ieşire $nfa.out$ se vor afla Q linii, pe fiecare dintre ele aflandu-se un numar 0 sau 1.
În fişierul de ieşire $nfa.out$ se vor afla $Q$ linii, pe fiecare dintre ele aflandu-se un numar $0$ sau $1$, a $i$-a valoare reprezentand acceptarea al celui de-al $i$-lea sir.
h2. Restricţii
* $1 ≤ N ≤ 100.000$ ; $1 ≤ N ≤ 400.000$
* Pentru 50 de puncte $1 ≤ N ≤ 1.000$ ; $1 ≤ N ≤ 4.000$
* NFA-ul dat are o singura stare initiala
* $1 ≤ N ≤ 300$
* $1 ≤ M ≤ 1.200$
* $1 ≤ Q ≤ 50$
* Lungimea cuvintelor este mai mica decat 150.
* Pentru 20 de puncte $1 ≤ N ≤ 10$ ; $1 ≤ M ≤ 40$ ; $1 ≤ Q ≤ 5$ ; lungimea cuvintelor este mai mica decat 20.
* Pentru alte 30 de puncte $1 ≤ N ≤ 50$ ; $1 ≤ M ≤ 200$ ; lungimea cuvintelor este mai mica decat 100.
* Pentru alte 30 de puncte $1 ≤ N ≤ 100$ ; $1 ≤ M ≤ 400$
* NFA-ul dat are o singura stare initiala.
h2. Exemplu
table(example). |_. nfa.in |_. nfa.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5 2
3
2 5
3 1 a
1 2 b
2 1 a
3 5 a
5 4 d
7
ab
aba
abab
ad
nuchichi
a
dausu
| 1
0
1
0
0
1
0
|
h3. Explicaţie
...
!problema/nfa?lfa.png 50*100!
Informal, trebuie sa gasiti o parcurgere in graful dat plecand de la sursa si ajungand la un nod stare finala; in parcurgere literele de pe muchii trebuie sa respecte cuvantul (a i-a muchie sa aiba pe ea a i-a litera din cuvant).
== include(page="template/taskfooter" task_id="nfa") ==
