Fișierul intrare/ieșire	research.in, research.out	Sursă	ONI 2012 clasele 11-12
Autor	Vlad Duță	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.25 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	2.5

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Re-search (clasele 11-12)

Notă: Aceasta este o clonă a problemei Search (Infoarena) 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.

Date de intrare

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.

Date de ieșire

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.

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ă.

Exemplu

Explicație

...