Căutarea unei submatrice — potrivești un tipar dreptunghiular

De ce contează?

Cauți un mic logo pe o pagină scanată: îl pui într-un colț, verifici dacă se potrivește pixel cu pixel, iar dacă nu, îl muți cu o poziție și încerci din nou. Căutarea unei submatrice e exact asta — potrivești un dreptunghi mic peste unul mare.

Problema

Ai o matrice mare A (n × m) și un tipar P (p × q). Vrei să afli dacă P apare în A ca bloc dreptunghiular și unde anume.

P așezat cu colțul stânga-sus în (i, j) se potrivește dacă, pentru toate celulele lui:

P[x][y] == A[i+x][j+y]

Observația-cheie

Colțul tiparului nu poate fi oriunde: ultima linie de start e n - p, ultima coloană m - q. Altfel P ar depăși marginile lui A. Deci sunt (n-p+1)·(m-q+1) poziții de încercat.

Algoritmul naiv

Pentru fiecare colț (i, j) valid:

Compari toate cele p × q celule ale tiparului cu zona corespunzătoare din A.
La prima nepotrivire, abandonezi acel colț și treci la următorul.
Dacă toate se potrivesc → tiparul apare la (i, j).

Pas cu pas pe numere

A (3×3), tiparul P (2×2) = [[1,2],[3,1]]:

L0	5	1	2
	0	1	2

L1	9	3	1
	0	1	2

L2	4	0	7
	0	1	2

P se potrivește cu colțul în (0, 1): {1,2 / 3,1}

Colțul (0,0) dă {5,1 / 9,3} — nu se potrivește. Colțul (0,1) dă {1,2 / 3,1} — potrivire! Tiparul apare la (0, 1).

Implementare C++

#include <iostream>
using namespace std;

int A[100][100], P[100][100];

int main() {
    int n, m, p, q;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> A[i][j];
    cin >> p >> q;
    for (int x = 0; x < p; x++)
        for (int y = 0; y < q; y++) cin >> P[x][y];

    for (int i = 0; i <= n - p; i++)
        for (int j = 0; j <= m - q; j++) {
            bool ok = true;
            for (int x = 0; x < p && ok; x++)
                for (int y = 0; y < q; y++)
                    if (A[i + x][j + y] != P[x][y]) { ok = false; break; }
            if (ok) cout << "Submatrice gasita la (" << i << ", " << j << ")\n";
        }
    return 0;
}

Cele patru bucle: două pentru colț (i, j), două pentru verificarea celulelor (x, y) ale tiparului.

Complexitate

Caz	Timp	Spațiu
Cel mai rău	O(n·m·p·q)	O(1)
Tipic (nepotriviri rapide)	mult mai bun	O(1)

Pentru gimnaziu, când matricele sunt mici, costul e acceptabil. Algoritmi mai rapizi există, dar îi vei studia mai târziu.

Vizualizare

Urmărește cum tiparul P alunecă peste matricea A, colț cu colț, comparând celulele:

Greșeli frecvente

Greșeli frecvente de concurs:

Colțul iese din matrice. Buclele de start merg până la n - p și m - q (inclusiv). Dacă le duci până la n/m, accesezi A[i+x][j+y] în afara matricei.
Indexare relativă greșită. Celula tiparului P[x][y] se compară cu A[i+x][j+y], nu cu A[x][y]. Confuzia compară mereu același colț.
Nu abandonezi la prima nepotrivire. Fără ieșire rapidă verifici tot tiparul degeaba — corect ca rezultat, dar inutil de lent.
p > n sau q > m. Dacă tiparul e mai mare decât matricea, nu poate apărea. Buclele nici nu trebuie să pornească (n - p < 0).

Recapitulare

Cauți tiparul P (p×q) ca bloc dreptunghiular în A; sunt (n-p+1)·(m-q+1) colțuri posibile.
Pentru fiecare colț, compari P[x][y] cu A[i+x][j+y] și abandonezi la prima nepotrivire.
Naiv e O(n·m·p·q) — bun la gimnaziu; atenție la marginile n-p, m-q și la indexarea relativă.