uniolympiads English

Hashing συμβολοσειρών

Σύγκριση δύο οποιωνδήποτε υπολέξεων σε O(1)O(1), μετά από προεπεξεργασία O(n)O(n). Πιθανοτικό, με modulo 261−12^{61} - 1 και τυχαία βάση.

Πότε

Όταν χρειάζεσαι πολλές συγκρίσεις υπολέξεων και ο ντετερμινιστικός αλγόριθμος είναι δύσκολος: μακρύτερο παλίνδρομο με δυαδική αναζήτηση, μακρύτερη υπολέξη που εμφανίζεται δύο φορές, ελάχιστη περιστροφή.

Η ιδέα

Η λέξη γίνεται πολυώνυμο στη βάση bb, modulo έναν μεγάλο πρώτο pp:

h(s0…sk−1)=∑i=0k−1c(si) bk−1−i mod p.h(s_0 \dots s_{k-1}) = \sum_{i=0}^{k-1} c(s_i)\, b^{k-1-i} \bmod p .

Με τα hash των προθεμάτων HiH_i, το hash του sl…sr−1s_l \dots s_{r-1} είναι Hr−Hl br−l(modp)H_r - H_l\, b^{r-l} \pmod p, σε O(1)O(1).

Ίσες λέξεις δίνουν πάντα ίσο hash. Για δύο διαφορετικές λέξεις μήκους kk, η διαφορά των hash είναι ένα μη μηδενικό πολυώνυμο του bb βαθμού <k< k, με το πολύ k−1k - 1 ρίζες. Με τυχαίο bb η πιθανότητα σύγκρουσης είναι περίπου k/pk / p. Με p=261−1p = 2^{61} - 1 και 10610^{6} συγκρίσεις λέξεων μήκους 10610^{6}, αυτό είναι κάτω από 10−610^{-6}.

Ο πολλαπλασιασμός γίνεται σε 128 bit (__uint128_t). Το modulo με τον πρώτο Mersenne γίνεται με ολισθήσεις, χωρίς διαίρεση.

Γιατί τυχαία βάση

Με σταθερή βάση και modulo, κάποιος μπορεί να κατασκευάσει εκ των προτέρων δύο λέξεις με το ίδιο hash. Στο Codeforces αυτό γίνεται στα hacks: λύσεις με p=264p = 2^{64} (υπερχείλιση unsigned long long) πέφτουν πάντα με τη λέξη Thue–Morse. Η βάση εδώ διαλέγεται τη στιγμή που τρέχει το πρόγραμμα.

Παγίδες

  • Ο χαρακτήρας γίνεται c(si)=si+1c(s_i) = s_i + 1, ώστε το '\0' (ή το 'a' αν αφαιρέσεις 'a') να μη δίνει 0. Αλλιώς τα a\texttt{a} και aa\texttt{aa} θα είχαν το ίδιο hash.
  • Το test ελέγχει ότι ίσες υπολέξεις έχουν πάντα ίσο hash και ότι στις 2⋅1052 \cdot 10^5 συγκρίσεις διαφορετικών δεν υπήρξε σύγκρουση. Αυτό δεν αποδεικνύει ότι συγκρούσεις δεν γίνονται· τις κάνει απίθανες.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/string-hashing.cpp
// Polynomial string hashing modulo the Mersenne prime 2^61 - 1, with a random base.
// get(l, r) = hash of s[l..r) in O(1). Equal strings always have equal hashes; two different
// strings of length n collide with probability at most n / (2^61 - 1) over the choice of base.

struct StringHash {
    static constexpr unsigned long long MOD = (1ULL << 61) - 1;
    vector<unsigned long long> h;
    vector<unsigned long long> pw;

    static unsigned long long mul(unsigned long long a, unsigned long long b) {
        __uint128_t c = (__uint128_t)a * b;
        unsigned long long lo = (unsigned long long)(c & MOD);
        unsigned long long hi = (unsigned long long)(c >> 61);
        unsigned long long r = lo + hi;
        if (r >= MOD) {
            r -= MOD;
        }
        return r;
    }

    static unsigned long long base() {
        static unsigned long long b = 0;
        if (b == 0) {
            mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
            b = rng() % (MOD - 1000) + 500;
        }
        return b;
    }

    StringHash(const string& s) : h(s.size() + 1, 0), pw(s.size() + 1, 1) {
        unsigned long long b = base();
        for (size_t i = 0; i < s.size(); i++) {
            h[i + 1] = mul(h[i], b) + (unsigned char)s[i] + 1;
            if (h[i + 1] >= MOD) {
                h[i + 1] -= MOD;
            }
            pw[i + 1] = mul(pw[i], b);
        }
    }

    unsigned long long get(int l, int r) {
        unsigned long long x = h[r] + MOD - mul(h[l], pw[r - l]);
        if (x >= MOD) {
            x -= MOD;
        }
        return x;
    }
};

Ελέγχθηκε σε 1.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.