== include(page="template/taskheader" task_id="virus") ==
Poveste si cerinta...
Marian este programator la o firma ce produce software antivirus si a primit ca sarcina scrierea motorului de cautare al produsului. Firma fiind recent infiintata, analistii i-au pus la dispozitie doar un numar mic de virusi cunoscuti. Motorul va fi testat pe un sir de biti extras dintr-un executabil, trebuind sa produca o statistica care sa contina numarul de aparitii al fiecarui virus in sirul de biti.
Scrieti un program pentru a-l ajuta pe Marian sa obtina statistica ceruta.
h2. Date de intrare
Fisierul de intrare $virus.in$ ...
Fisierul de intrare $virus.in$ contine doua numere naturale $L$ si $N$, separate printr-un spatiu, $L$ reprezentand marimea sirului de biti, iar $N$ reprezentand numarul virusilor cunoscuti. A doua linie a fisierului contine un sir de lungime $L$, format doar din caracterele $'0'$ si $'1'$, reprezentand sirul de biti. Urmatoarele $2*N$ linii contin descrierea virusilor pusi la dispozitie de echipa de analisti. Fiecare virus este descris pe doua linii consecutive; prima dintre aceste linii contine un numar natural $k$ reprezentand lungimea acestui virus (exprimata in biti), iar a doua linie contine un sir de lungime $k$, format doar din caracterele $'0'$ si $'1'$, reprezentand descrierea lui.
h2. Date de iesire
In fisierul de iesire $virus.out$ ...
In fisierul de iesire $virus.out$ va contine exact $N$ linii. Pe fiecare linie se va scrie o valoare naturala reprezentand numarul de aparitii al fiecarui virus cunoscut, in ordinea data in fisierul de intrare.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1 000$
* $1 ≤ L ≤ 100 000$
* $1 ≤ k ≤ 1 000$
* Numarul total de aparitii nu va depasi $1 000 000$.
h2. Exemplu
table(example). |_. virus.in |_. virus.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7 3
0110101
5
11111
1
0
3
101
| 0
3
2
|
h3. Explicatie
...
Sunt $3$ virusi. Primul virus din fisier, $11111$, nu apare in sirul de biti , astfel se va scrie valoarea $0$ pe prima linie a fisierului $virus.out$. Cel de-al doilea virus din fisier, $0$, apare in sirul de biti de $3$ ori (pozitiile $1, 4$ si {$6$}), astfel se va scrie valoarea $3$ pe a doua linie a fisierului $virus.out$. Ultimul virus din fisier, $101$, apare in sirul de biti de $2$ ori (incepand cu pozitiile $3$ si {$5$}), astfel se va scrie valoarea $2$ pe a treia linie a fisierului $virus.out$.
== include(page="template/taskfooter" task_id="virus") ==
