Résolution Efficace des Problèmes de Correspondance Matricielle

Lorsqu'il s'agit de déterminer si une sous-structure spécifique apparaît dans une grande grille de caractères ou de chiffres, les méthodes naïves comportant une complexité quadratique deviennent prohibitives. Une approche optimale consiste à appliquer un algorithme de hachage polynomial, communément appelé Rabin-Karp, adapté au contexte bidimensionnel.

L'idée centrale repose sur la décomposition de la représentation 2D en séquences unidimensionnelles gérables. Plutôt que de traiter la matrice comme un simple flux linéaire, nous calculons des sommes préfixées en deux passes distinctes : horizontale puis verticale. Cette méthode garantit que chaque sous-bloc cnoserve son identité unique sans collision excessive.

Construction des Préfixes de Hash

Pour initialiser efficacement les recherches, nous devons construire une table de hachage accumulée. Nous utilisons deux constantes premières distinctes pour éviter les biais :

• Base Horizontale (ex: 131) : Combine les éléments d'une ligne vers la droite.
• Base Verticale (ex: 137) : Combine les lignes entre elles pour former une colonne logique.

La valeur de hachage pour une cellule (r, c) se calcule ainsi :

1. Passage horizontal : rowHash[r][c] = rowHash[r][c-1] * Base_H + Valeur(r,c)
2. Passage vertical : totalHash[r][c] = totalHash[r-1][c] * Base_V + rowHash[r][c]

Ce processus permet d'obtenir, pour n'importe quel rectangle borné par (r1, c1) et (r2, c2), une signature numérique représentative de ce contenu en temps constant, après les précalculs initiaux.

Extraction du Hash d'un Sous-Bloc

Une fois les tables construites, extraire le hachage d'une zone rectangulaire s'apparente à une formule d'inclusion-exclusion. Si H[x][y] représente le hachage cumulatif jusqu'à la ligne x et la colonne y, le hachage du bloc défini par les coins supérieurs gauche et inférieur droit est donné par :

uint64_t extract(int r, int c, int w, int h) {
    uint64_t res = H[r][c];
    
    // Retirer la partie supérieure déplacée verticalement
    res -= H[r-w][c] * Pow_V[w]; 
    
    // Retirer la partie droite déplacée horizontalement
    res -= H[r][c-h] * Pow_H[h]; 
    
    // Ajouter l'intersection retranchée deux fois
    res += H[r-w][c-h] * Pow_V[w] * Pow_H[h];
    
    return res;
}

L'utilisation de la surcharge naturelle des types entiers non signés (unsigned long long) simule une arithmétique modulo $2^{64}$, éliminant ainsi le besoin de coûteuses opérations de modulo explicites tout en gardant les risques de collisions très faibles pour les problèmes pratiques.

Stratégie d'Implémentation

Dans le cadre de la résolution de ce type de problème, nous stockons les signatures de toutes les sous-matrices possibles de dimension requise ($A \times B$) dans une liste triée. Les requêtes ultérieures sont ensuite résolues par recherche binaire.

Voici une implémentation moderne utilisant le standard C++, avec une gestion claire des puissances et des entrées/sorties :

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Configuration des paramètres constants
const int MAX_DIM = 1005;
const unsigned long long BASE_COL = 131ULL; 
const unsigned long long BASE_ROW = 137ULL;

unsigned long long powCol[MAX_DIM];
unsigned long long powRow[MAX_DIM];
unsigned long long prefHash[MAX_DIM][MAX_DIM];
unsigned long long targetSignatures[MAX_DIM * MAX_DIM];
int cntTarget = 0;

char grid[MAX_DIM][MAX_DIM];

void initPowers(int maxLen) {
    powCol[0] = 1;
    powRow[0] = 1;
    for (int i = 1; i <= maxLen; ++i) {
        powCol[i] = powCol[i-1] * BASE_COL;
        powRow[i] = powRow[i-1] * BASE_ROW;
    }
}

void buildHash(int rows, int cols) {
    // Étape 1 : Somme préfixe horizontale par ligne
    for (int r = 1; r <= rows; ++r) {
        for (int c = 1; c <= cols; ++c) {
            prefHash[r][c] = prefHash[r][c-1] * BASE_ROW + (unsigned long long)grid[r][c];
        }
    }

    // Étape 2 : Somme préfixe verticale sur les résultats précédents
    for (int c = 1; c <= cols; ++c) {
        for (int r = 1; r <= rows; ++r) {
            prefHash[r][c] = prefHash[r-1][c] * BASE_COL + prefHash[r][c];
        }
    }
}

unsigned long long getSubHash(int r, int c, int h, int w) {
    // Application de la formule d'extraction pour le rectangle en bas-droite (r,c)
    // Dimensions h x w
    unsigned long long val = prefHash[r][c];
    
    // Soustraction des zones externes corrigées par les puissances des bases
    val -= prefHash[r-h][c] * powCol[h];
    val -= prefHash[r][c-w] * powRow[w];
    val += prefHash[r-h][c-w] * powCol[h] * powRow[w];
    
    return val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C, targetR, targetC;
    if (!(cin >> R >> C >> targetR >> targetC)) return 0;

    initPowers(max(R, C));

    // Lecture de la matrice principale
    for (int r = 1; r <= R; ++r) {
        cin >> (grid[r]+1);
    }

    // Construction de la table de hachage globale
    buildHash(R, C);

    // Collecte de tous les motifs possibles de taille cible
    vector<unsigned long=""> storedTargets;
    for (int i = targetR; i <= R; ++i) {
        for (int j = targetC; j <= C; ++j) {
            storedTargets.push_back(getSubHash(i, j, targetR, targetC));
        }
    }

    // Tri pour permettre la recherche dichotomique
    sort(storedTargets.begin(), storedTargets.end());
    storedTargets.erase(unique(storedTargets.begin(), storedTargets.end()), storedTargets.end());

    int q;
    cin >> q;
    while(q--) {
        // Lecture du motif de requête et calcul de son hash
        unsigned long long currentHash = 0;
        
        // Réinitialisation temporaire pour le calcul local du motif
        for (int r = 0; r < targetR; ++r) {
            string rowPattern;
            cin >> rowPattern;
            unsigned long long rowVal = 0;
            for (char c : rowPattern) {
                rowVal = rowVal * BASE_ROW + (unsigned long long)c;
            }
            currentHash = currentHash * BASE_COL + rowVal;
        }

        // Vérification d'existence
        bool found = binary_search(storedTargets.begin(), storedTargets.end(), currentHash);
        cout << (found ? "1\n" : "0\n");
    }
    return 0;
}
</unsigned>

Cette approche garantit une précision optimale tout en minimisant la consommation mémoire. En pré-calculant toutes les positions potentielles, la réponse à chaque interrogation devient logarithmique par rapport à la taille de la matrice, rendant la solution viable même pour des datasets massifs.