Fişierul intrare/ieşire:matrix.in, matrix.outSursăpreONI 2006 Runda 4
AutorSilviu-Ionut Ganceanu, Tiberiu-Lucian FloreaAdăugată de
Timp execuţie pe test0.45 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

Exemplu

matrix.inmatrix.out
3 2
acb
bda
acb
ab
cd
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content