== include(page="template/taskheader" task_id="research") ==
Poveste și cerință...
*Notă:* Aceasta este o clonă a problemei Search ("Infoarena":http://www.infoarena.ro/problema/search) cu limita de memorie mult mai mică.
Pojărel are o listă de $N$ fișiere, fiecare având numele format doar din litere mici ale alfabetului latin. El vrea să implementeze un motor de căutare care să funcționeze în timp real, adică imediat ce utilizatorul inserează sau șterge o literă din câmpul de căutare, să i se returneze numărul de fișiere care corespund șirului introdus la momentul respectiv. Un fișier corespunde căutării dacă numele acestuia conține șirul căutat ca subșir. Mai precis, caracterele din câmpul de căutare trebuie să apară în numele fișierului în aceeași ordine, însă nu neapărat pe poziții consecutive.
Fiind dată lista care conține numele fișierelor, determinați numărul de fișiere care va fi returnat după fiecare introducere sau ștergere a unui caracter din câmpul de căutare.
h2. Date de intrare
Fișierul de intrare $research.in$ ...
Fișierul de intrare $research.in$ conține pe prima linie două numere naturale $N$ și [$M$], reprezentând numărul de fișiere, respectiv numărul de operații care se fac asupra câmpului de căutare. Pe următoarele $N$ linii se găsesc cele $N$ nume de fișiere, formate doar din litere mici ale alfabetului latin. Urmează apoi $M$ linii care descriu operațiile în ordinea în care sunt efectuate. Astfel, pe fiecare linie $i$ se află un singur caracter care descrie operația [$i$]. Acest caracter este fie o literă, ceea ce înseamnă că s-a introdus litera respectivă în câmpul de căutare, fie caracterul $'-'$ , ceea ce înseamnă că s-a șters ultima literă din câmpul de căutare.
h2. Date de ieșire
În fișierul de ieșire $research.out$ ...
Fișierul de ieșire $research.out$ va conține $M$ linii. Pe linia $i (1 ≤ i ≤ M)$ se va afișa numărul de fișiere returnate de motorul de căutare după efectuarea primelor $i$ operații.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100$
* $1 ≤ M ≤ 200.000$
* lungimea oricărui nume de fișier este maxim 5.000;
* două sau mai multe fișiere pot avea același nume;
* prima litera introdusă nu va fi ștearsă niciodată.
h2. Exemplu
table(example).
|_. research.in |_. research.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. research.in |_. research.out |_. Explicații |
| 4 5
palalila
alabala
olimpiada
iasi
a
a
l
-
b
| 4
3
2
3
1
| * prima dată se introduce litera a, care se găsește în toate cele 4 nume de fișiere
* după a doua operație câmpul va avea valoarea aa și vor fi găsite primele 3 fișiere
* după a treia operație câmpul va avea valoarea aal și vor fi găsite fișierele palalila și alabala
* după a patra operație câmpul va avea din nou valoarea aa și vor fi găsite primele 3 fișiere
* după a cincea operație câmpul va avea valoarea aab și va fi găsit doar fișierul alabala
|
== include(page="template/taskfooter" task_id="research") ==
