Fişierul intrare/ieşire:fotografie.in, fotografie.outSursăad-hoc
AutorclasicaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.1 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.infotografie.out
6 8
ababaccb
cdcdcacd
bbbcbabb
aababaab
ccdcdcbd
bbcbcbda
3 3
aba
cdc
bcb
0 2
3 1
3 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici