Fişierul intrare/ieşire:research.in, research.outSursăONI 2012 clasele 11-12
AutorVlad DutaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

research.inresearch.outExplicaţ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
Trebuie sa te autentifici pentru a trimite solutii. Click aici