== include(page="template/taskheader" task_id="fotografie") ==
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 $A[~i,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 $B[~i,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. Spunem că $B$ apare în $A$ cu translația $(dl, dc)$ dacă $B[~i,j~] = A[~dl + i, dc + j~]$, pentru orice $1 ≤ i ≤ P$ și $1 ≤ j ≤ Q$.
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 $A[~i,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 $B[~i,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ă $B[~i,j~] = A[~dl + i, dc + j~]$, pentru orice $1 ≤ i ≤ P$ și $1 ≤ j ≤ Q$.
h2. Date de intrare
Fișierul de intrare $fotografie.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $fotografie.out$ ...
Î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$].
h2. 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ă.
h2. Exemplu
table(example).
|_. fotografie.in |_. fotografie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 8
ababaccb
cdcdcacd
bbbcbabb
aababaab
ccdcdcbd
bbcbcbda
3 3
aba
cdc
bcb
| 0 2
3 1
3 3
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="fotografie") ==
