.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » virus

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
virus


Timp maxim de execuţie / test:
0.7s
Memorie totala disponibilă / stivă:
96MB / 1MB

Marian este programator la o firmă ce produce software antivirus şi a primit ca sarcină scrierea motorului de căutare al produsului. Firma fiind recent înfiinţată, analiştii i-au pus la dispoziţie doar un număr mic de viruşi cunoscuţi. Motorul va fi testat pe un şir de biţi extras dintr-un executabil, trebuind să producă o statistică care să conţină numărul de apariţii al fiecărui virus în şirul de biţi.

Cerinţă

Scrieţi un program pentru a-l ajuta pe Marian să obţină statistica cerută.

Date de intrare

Prima linie a fişierul de intrare virus.in conţine două numere naturale L şi N, separate printr-un spaţiu, L reprezentând mărimea şirului de biţi, iar N reprezentând numărul viruşilor cunoscuţi. A doua linie a fişierului conţine un şir de lungime L, format doar din caracterele ′0′ şi ′1′, reprezentând şirul de biţi. Următoarele 2*N linii conţin descrierea viruşilor puşi la dispoziţie de echipa de analişti. Fiecare virus este descris pe două linii consecutive; prima dintre aceste linii conţine un număr natural k reprezentând lungimea acestui virus (exprimată în biţi), iar a doua linie conţine un şir de lungime k, format doar din caracterele ′0′ şi ′1′, reprezentând descrierea lui.

Date de ieşire

Fişierul de ieşire virus.out va conţine exact N linii. Pe fiecare linie se va scrie o valoare naturală reprezentând numărul de apariţii al fiecărui virus cunoscut, în ordinea dată în fişierul de intrare.

Restricţii

• 1 ≤ N ≤ 1000
• 1 ≤ L ≤ 100000
• 1 ≤ k ≤ 1000

• Numărul total de apariţii nu va depăşi 1000000

Exemple

virus.invirus.outExplicaţii
7 3 0110101 5 11111 1 0 3 101 0 3 2 Sunt 3 viruşi. Primul virus din fişier, 11111, nu apare în şirul de biţi , astfel se va scrie valoarea 0 pe prima linie a fişierului virus.out. Cel de-al doilea virus din fişier, 0, apare în şirul de biţi de 3 ori (poziţiile 1, 4 şi 6), astfel se va scrie valoarea 3 a doua linie a fişierului virus.out. Ultimul virus din fişier, 101, apare în şirul de biţi de 2 ori (începând cu poziţiile 3 şi 5), astfel se va scrie valoarea 2 pe a treia linie a fişierului virus.out.

autor: Prof. Csaba Pătcaş
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
Chestionare recomandate
surse trimise | ajutor