Search

search

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

p<>. 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ăutarii 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.
 
h2. Cerinţă
 
p<>. 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.

Poveste şi cerinţă...

h2. Date de intrare

p<>. Fişierul de intrare $search.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 afla 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.

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

h2. Date de ieşire

Fişierul de ieşire $search.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.

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

h2. Restricţii

* $1 ≤ N ≤ 100$
* $1 ≤ M ≤ 200 000$
* lungimea oricărui nume de fişier este maxim $5000$;
* două sau mai multe fişiere pot avea acelaşi nume;
* prima litera introdusă nu va fi ştearsă niciodată.

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

h2. Exemplu

table(example). |_. search.in |_. search.out |_. Explicaţie |
| 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 p{*a*}l{*a*}li{*l*}a şi al{*a*}b{*al*}a
- 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 {*a*}l{*ab*}ala
|

table(example). |_. search.in |_. search.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

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

7743