matrix

Matrix

== include(page="template/taskheader" task_id="matrix") ==

==Include(page="template/taskheader" task_id="matrix")==

Poveste ...

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.

h2. Cerinta

...

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

h2. Restrictii

h2. 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

h2. Date de intrare

h2. Date de Iesire

...

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

h2. Date de iesire

h2. 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.

h2. Exemplu

| matrix.in | matrix.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. matrix.in |_. matrix.out |
| 3 2
  acb
  bda
  acb
  ab
  cd
| 4 |

== include(page="template/taskfooter" task_id="matrix") ==

==Include(page="template/taskfooter" task_id="matrix")==
 
 

846