c3selector

B. C3Selector

== include(page="template/taskheader" task_id="c3selector") ==

Poveste şi cerinţă...

Probabil toata lumea a auzit despre pagini web si a vazut tag-uri HTML. La o firma de software din Cluj unde algoritmii intalnesc tehnologia, numita fictiv AlgoTech, una din intrebarile de la interviuri le cere candidatilor sa implementeze un selector de CSS.
 
O pagina HTML este considerata valida daca respecta urmatoarele conditii:
 
* are un singur tag parinte; toate celelalte tag-uri sunt copii directi sau indirecti ai tag-ului parinte
* toate tag-urile se deschid cu $<tagname>$ si se inchid cu $</tagname>$
* un tag poate avea oricati copii, putand avea forma: $<x><y><y></y></y><z></z></x>$
* un tag poate avea un atribut suplimentar class, avand forma: $<tagname class=“classx classy”>$
* este posibil ca unele din tag-urile terminale (care nu mai au copii) sa contina un text, putand avea forma: $<x><y>text</y><z><y><x>another text</x></y></z></x>$
* acelasi tag poate aparea de mai multe ori, posibil cu clase diferite, dar intotdeauna se inchid corect
* o clasa poate aparea de mai multe ori, posibil la tag-uri diferite
 
Un selector CSS este un pattern folosit pentru a identifica tag-uri intr-un HTML. El poate avea urmatoarele forme:
 
* $div$ = selecteaza toate tag-urile cu numele div
* $div p$ = selecteaza toate tag-urile p care se afla in interiorul unui tag div
* $.intro$ = selecteaza toate tag-urile care au clasa intro
* $.intro.layout$ = selecteaza toate tag-urile care au atat clasa intro cat si clasa layout ( _atentie: este posibil sa apara mai mult de doua clase_ )
* $.layout .header$ = selecteaza toate tag-urile care au clasa header si se afla in interiorul unui tag care are clasa layout ( _atentie: intre cele doua clase exista un spatiu_ )
* $p.big$ = selecteaza toate tag-urile p care au clasa big
* $p .big$ = selecteaza toate tag-urile cu clasa big care se afla in interiorul unui tag p ( _atentie: intre tag si clasa exista un spatiu_ )
 
Pe baza formelor mentionate mai sus, un selector CSS poate lua toate combinatiile lor, putand avea orice forma. Exemplu: $div.a p.q.b i.icon.q.red x y z.x.y.z.a .a.b.c d$
 
Dându-se **T** teste, fiecare avand o pagina HTML valida si **Q** selectoare, sa se spuna pentru fiecare selector cate tag-uri distincte poate identifica.

h2. Date de intrare

Fişierul de intrare $c3selector.in$ ...

Fişierul de intrare $c3selector.in$ conţine pe prima linie numărul **T**, iar pe urmatoarele linii sunt descrise cele **T** teste. Fiecare test ocupa mai multe linii, in felul urmator:
 
* O linie avand valoarea **Q**
* O linie avand un sir de caractere reprezentand un HTML valid
* **Q** linii avand cate un sir de caractere reprezentant un selector CSS

h2. Date de ieşire

În fişierul de ieşire $c3selector.out$ ...

În fişierul de ieşire $c3selector.out$ trebuie sa afisati mai multe linii. Pe fiecare linie se afla un singur numar, reprezentand raspunsul la cate un selector din fisierul de intrare. Raspunsurile trebuie sa apara in ordinea intrebarilor din fisierul de intrare.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

* $T <= 5$
* $1 <= Q <= 1000$
* HTML-ul nu poate avea mai mult de $100$ de tag-uri
* Lungimea HTML-ului nu poate avea mai mult de $10.000$ de caractere
* Lungimea unui selector CSS nu poate avea mai mult de $500$ de caractere
* Numele unui tag nu poate avea mai mult de $10$ de caractere
* Numele unei clase nu poate avea mai mult de $10$ de caractere
* HTML-ul poate contine doar: litere mici ale alfabetului englez, $<$, $>$, $/$, $=$, $"$ sau spatii

h2. Exemplu
table(example). |_. c3selector.in |_. c3selector.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
4
<div class="a"><span class="q w">text</span><p class="q b"><i class="icon q red"></i></p></div>
div p.b
.a .q
div.a p.q.b i.icon.q.red
div span
10
<div class="a"><ul><li class="a"></li><li class="b"></li><li></li></ul><span class="q w">text</span><p class="q b"><i class="icon q red"></i></p></div>
div.a p.q.b i.icon.q.red
div p.b
.a .q
div span
ul li
div li
.a
.a .a
.a ul li.a
ul span.w
| 1
3
1
1
1
1
3
1
3
3
2
1
1
0

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="c3selector") ==