Pagini recente » Diferente pentru problema/pang intre reviziile 4 si 5 | Diferente pentru utilizator/challenge intre reviziile 2 si 3 | Diferente pentru problema/bstrings intre reviziile 2 si 4 | Diferente pentru problema/zeroc intre reviziile 4 si 5 | Matrix

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 16:43:17.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	matrix.in, matrix.out	Sursă	preONI 2006 Runda 4
Autor	Silviu-Ionut Ganceanu, Tiberiu-Lucian Florea	Adăugată de
Timp execuţie pe test	0.225 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	2/5

Matrix

Cercetatorii din tara lui Papura-Voda au descoperit harta genomului uman si au reprezantat-o ca matrice de dimensiuni MxM ce contine litere mici ale alfabetului englez. O specie extrateresta a atacat umanitatea, utilizand un virus a carui definitie a fost identificata, de aceeasi bravi cercetatori, sub forma unei matrici de dimensiuni NxN care contine tot litere mici ale alfabetului englez. Cercetatorii vor sa afle gradul de infestare a genomului uman, care se masoara in numarul de aparitii a definitiei virusului in harta acestuia. Problema este insa ceva mai complicata, deoarece virusul se poate deghiza interschimband de oricate ori, oricare doua pozitii din matricea care il defineste.

Cerinta

Determinati numarul de aparitii (incluzandu-le si pe cele deghizate) ale definitiei virusului in harta genomului uman.

Date de Intrare

Prima linie contine doua numere, M si N, cu semnificatia de mai sus. Urmeaza M linii continand cate M caractere (fara spatii) reprezentand harta genomului uman. Urmatoarele N linii contin N caractere (fara spatii) reprezentand definitia virusului

Date de Iesire

Fisierul de iesire va contine pe prima linie numarul de aparitii ale virusului (eventual deghizat) in harta genomului uman.

Restrictii si precizari

1 ≤ N ≤ M ≤ 1000
Ambele matrici contin litere mici ale alfabetului englez
Doua aparitii diferite ale virusului se pot suprapune partial (vezi exemplul)
Pentru 50% din teste M <= 200
Nu stiu daca se poate identifica un virus analizand harta genomului uman. Povestea e pura fictiune. Orice asemanare cu realitatea este intamplatoare si neintentionata.