Le hachage de chaînes est une technique algorithmique puissante qui permet de transformer une séquence de caractères en une valeur numérique unique (ou presque). Cette méthode est particulièrement efficace pour effectuer des comparaisons de sous-chaînes en temps constent \(O(1)\) après un prétraitement en \(O(n)\). Elle trouve ses applications dans la recherche de motifs, la détection de répétitions et les problèmes de bio-informatique.

Hachage simple avec modulo

Cette approche utilise un polynôme où chaque caractère de la chaîne est pondéré par une base élevée à une certaine puissance, le tout réduit par un nombre premier (modulo). La structure ci-dessous permet de calculer rapidement le hachage de n'importe quel segment [gauche, droite].

#include <vector>
#include <string>

class GenerateurHachage {
private:
    using i64 = long long;
    std::vector<i64> hachages; 
    std::vector<i64> puissances;
    i64 base_val;
    i64 mod_val;

public:
    GenerateurHachage(const std::string& texte, i64 base = 131, i64 mod = 1e9 + 7) 
        : base_val(base), mod_val(mod) {
        int longueur = texte.size();
        hachages.assign(longueur + 1, 0);
        puissances.assign(longueur + 1, 1);

        for (int i = 0; i < longueur; ++i) {
            // Calcul du préfixe : (précédent * base + caractère actuel) % modulo
            hachages[i + 1] = (hachages[i] * base_val + texte[i]) % mod_val;
            puissances[i + 1] = (puissances[i] * base_val) % mod_val;
        }
    }

    // Récupère la valeur de hachage pour l'intervalle [l, r] inclus (0-indexed)
    i64 calculerSegment(int l, int r) {
        i64 segment = (hachages[r + 1] - hachages[l] * puissances[r - l + 1] % mod_val) % mod_val;
        return (segment < 0) ? (segment + mod_val) : segment;
    }
};

Technique du débordement naturel

Pour optimiser les performances, on peut utiliser le type unsigned long long en C++. Dans ce cas, le modulo est implicitement fixé à \(2^{64}\) grâce au mécanisme de débordemant d'entier (overflow). Cela simplifie le code et accélère l'exécution en évitant les opérations de division/modulo explicites.

class HachageRapide {
private:
    using u64 = unsigned long long;
    std::vector<u64> sommets;
    std::vector<u64> facteurs;
    u64 multiplicateur;

public:
    HachageRapide(const std::string& s, u64 base = 13331) : multiplicateur(base) {
        int n = s.length();
        sommets.resize(n + 1, 0);
        facteurs.resize(n + 1, 1);

        for (int i = 0; i < n; ++i) {
            sommets[i + 1] = sommets[i] * multiplicateur + s[i];
            facteurs[i + 1] = facteurs[i] * multiplicateur;
        }
    }

    u64 extraire(int debut, int fin) {
        // Formule simplifiée sans modulo explicite
        return sommets[fin + 1] - sommets[debut] * facteurs[fin - debut + 1];
    }
};

Le Double Hachage pour minimiser les collisions

Bien que le hachage simple soit efficace, il existe un risque de collisions (deux chaînes différentes produisant le même hachage). Le double hachage réduit drastiquement cette probabilité en utilisant deux paires de bases et de modulos différents simultanément.

#include <utility>

class DoubleHachage {
private:
    struct MoteurHachage {
        std::vector<long long> pref, pwr;
        long long b, m;

        MoteurHachage(const std::string& s, long long base, long long mod) : b(base), m(mod) {
            int len = s.size();
            pref.assign(len + 1, 0);
            pwr.assign(len + 1, 1);
            for (int i = 0; i < len; ++i) {
                pref[i + 1] = (pref[i] * b + s[i]) % m;
                pwr[i + 1] = (pwr[i] * b) % m;
            }
        }

        long long obtenir(int i, int j) {
            long long v = (pref[j + 1] - pref[i] * pwr[j - i + 1] % m) % m;
            return v < 0 ? v + m : v;
        }
    };

    MoteurHachage h1, h2;

public:
    DoubleHachage(const std::string& source) 
        : h1(source, 131, 1000000007), 
          h2(source, 137, 1000000009) {}

    // Retourne une paire de valeurs de hachage
    std::pair<long long, long long> hacherRange(int i, int j) {
        return {h1.obtenir(i, j), h2.obtenir(i, j)};
    }
};

// Exemple d'utilisation pour comparer deux sous-chaînes
void verifierIdentite(DoubleHachage& dh, int l1, int r1, int l2, int r2) {
    if (dh.hacherRange(l1, r1) == dh.hacherRange(l2, r2)) {
        // Les sous-chaînes sont considérées comme identiques avec une haute probabilité
    }
}