Fișierul intrare/ieșire | fotografie.in, fotografie.out | Sursă | ad-hoc |
---|---|---|---|
Autor | clasică | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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 |