Fișierul intrare/ieșire fotografie.in, fotografie.out Sursă ad-hoc
Autor clasică Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.1 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Fotografie (clasele 9-10)

O fotografie dreptunghiulară A constă din M linii și N coloane de pixeli. Fotografia conține cel mult 26 de culori, codificate prin litere mici ale alfabetului latin. Notăm cu Ai,j pixelul de pe linia i și coloana j (numerotarea se face începând de la 1). Similar, avem o fotografie mai mică B de P x Q pixeli, unde notăm cu Bi,j pixelul de pe linia i și coloana j. Dorim să căutăm toate aparițiile lui B în A. Fotografiile au orientări cunoscute și nu pot fi rotite, ci doar translatate. Pentru 0 ≤ dl ≤ M – P și 0 ≤ dc ≤ N – Q, spunem că B apare în A cu translația (dl, dc) dacă Bi,j = Adl + i, dc + j, pentru orice 1 ≤ i ≤ P și 1 ≤ j ≤ Q.

Date de intrare

Fișierul de intrare fotografie.in conține pe prima linie numerele M N, despărțite printr-un spațiu. Pe următoarele M linii se află câte N litere mici, reprezentând pixelii fotografiei A. Pe următoarea linie se află numerele P Q, despărțite printr-un spațiu. Pe următoarele P linii se află câte Q litere mici, reprezentând pixelii fotografiei B.

Date de ieșire

În fișierul de ieșire fotografie.out se vor scrie atâtea linii câte apariții are B în A. Pe fiecare linie se va scrie o pereche de numere reprezentând o translație la care B apare în A. Translațiile vor fi ordonate după valoarea lui dl, iar ca al doilea criteriu după valoarea lui dc.

Restricții

  • 1 ≤ M, N ≤ 1.000
  • 1 ≤ P ≤ M
  • 1 ≤ Q ≤ N
  • Se garantează că B apare în A cel puțin o dată.

Exemplu

fotografie.in fotografie.out
6 8
ababaccb
cdcdcacd
bbbcbabb
aababaab
ccdcdcbd
bbcbcbda
3 3
aba
cdc
bcb
0 2
3 1
3 3

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii