Hashing συμβολοσειρών
Σύγκριση δύο οποιωνδήποτε υπολέξεων σε , μετά από προεπεξεργασία . Πιθανοτικό, με modulo και τυχαία βάση.
Πότε
Όταν χρειάζεσαι πολλές συγκρίσεις υπολέξεων και ο ντετερμινιστικός αλγόριθμος είναι δύσκολος: μακρύτερο παλίνδρομο με δυαδική αναζήτηση, μακρύτερη υπολέξη που εμφανίζεται δύο φορές, ελάχιστη περιστροφή.
Η ιδέα
Η λέξη γίνεται πολυώνυμο στη βάση , modulo έναν μεγάλο πρώτο :
Με τα hash των προθεμάτων , το hash του είναι , σε .
Ίσες λέξεις δίνουν πάντα ίσο hash. Για δύο διαφορετικές λέξεις μήκους , η διαφορά των hash είναι ένα μη μηδενικό πολυώνυμο του βαθμού , με το πολύ ρίζες. Με τυχαίο η πιθανότητα σύγκρουσης είναι περίπου . Με και συγκρίσεις λέξεων μήκους , αυτό είναι κάτω από .
Ο πολλαπλασιασμός γίνεται σε 128 bit (__uint128_t). Το modulo με τον πρώτο Mersenne γίνεται με ολισθήσεις, χωρίς διαίρεση.
Γιατί τυχαία βάση
Με σταθερή βάση και modulo, κάποιος μπορεί να κατασκευάσει εκ των προτέρων δύο λέξεις με το ίδιο hash. Στο Codeforces αυτό γίνεται στα hacks: λύσεις με (υπερχείλιση unsigned long long) πέφτουν πάντα με τη λέξη Thue–Morse. Η βάση εδώ διαλέγεται τη στιγμή που τρέχει το πρόγραμμα.
Παγίδες
- Ο χαρακτήρας γίνεται , ώστε το
'\0'(ή το'a'αν αφαιρέσεις'a') να μη δίνει 0. Αλλιώς τα και θα είχαν το ίδιο hash. - Το test ελέγχει ότι ίσες υπολέξεις έχουν πάντα ίσο hash και ότι στις συγκρίσεις διαφορετικών δεν υπήρξε σύγκρουση. Αυτό δεν αποδεικνύει ότι συγκρούσεις δεν γίνονται· τις κάνει απίθανες.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- String Matching · String Algorithms
- Longest Palindrome · String Algorithms
Περισσότερα στο USACO Guide
- Hashing · usaco.guide/gold/hashing
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.