Programare Competitivă

Algoritmul Rabin-Karp (hashing pe șiruri)

Rabin-Karp este un algoritm pentru căutarea unui subșir într-un șir mare, folosind hashing.

În loc să comparăm caracter cu caracter (O(n*m)), calculăm un hash pentru fiecare fereastră de lungime m și îl comparăm cu hash-ul șablonului. Comparația devine O(1) per fereastră.

Problema

Avem un text s de lungime n și un șablon p de lungime m. Vrem să găsim toate aparițiile lui p în s.

s = "abcabcabd"
p = "abc"

Apariții: pozițiile 0 și 3

Soluție naivă O(n*m)

Pentru fiecare poziție din s, comparăm cu p. Lent pentru șiruri mari.

Ideea Rabin-Karp

Hash-ul unui șir e un număr care îl reprezintă. Două șiruri identice au același hash.

  1. Calculăm hash-ul lui p - hashP.
  2. Calculăm hash-ul primei ferestre de lungime m din s - hashS.
  3. Glisăm fereastra prin s, actualizând hash-ul incremental (O(1) per pas).
  4. Dacă hash-urile sunt egale, verificăm caracter cu caracter (să evităm coliziunile).

Complexitate medie: O(n + m).

Hash polinomial

Cel mai folosit tip de hash pentru șiruri:

hash(s) = s[0] * B^(m-1) + s[1] * B^(m-2) + ... + s[m-1] (mod MOD)

Unde: - B = baza (un număr prim, de ex. 31 sau 131) - MOD = un număr mare prim (de ex. 10^9 + 7)

De ce mod MOD?

Hash-urile pot fi foarte mari. mod le ține în limitele int / long long și distribuie uniform valorile.

Actualizarea hash-ului la glisare

Când fereastra glisează cu o poziție la dreapta: - Scoatem primul caracter (cel de la stânga) - Adăugăm noul caracter (cel de la dreapta)

Fereastră: [a b c] a b c a b d
            ^
           hash_vechi

După shift:
Fereastră:  a [b c a] b c a b d
                ^
              hash_nou

hash_nou = (hash_vechi - a * B^(m-1)) * B + caracter_nou  (mod MOD)

Cod

#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const long long MOD = 1000000007;
const long long B = 131;

char s[1000001];
char p[1001];

int main()
{
    fin >> s >> p;

    int n = strlen(s);
    int m = strlen(p);

    if (m > n) return 0;

    // Calculăm B^(m-1) mod MOD
    long long power = 1;
    for (int i = 0; i < m - 1; i++)
        power = (power * B) % MOD;

    // Hash-ul lui p
    long long hashP = 0;
    for (int i = 0; i < m; i++)
        hashP = (hashP * B + p[i]) % MOD;

    // Hash-ul primei ferestre din s
    long long hashS = 0;
    for (int i = 0; i < m; i++)
        hashS = (hashS * B + s[i]) % MOD;

    // Verificăm prima fereastră
    if (hashS == hashP) {
        // Verificăm caracter cu caracter (ca să evităm coliziuni)
        bool match = true;
        for (int i = 0; i < m; i++)
            if (s[i] != p[i]) { match = false; break; }
        if (match) fout << 0 << " ";
    }

    // Glisăm fereastra
    for (int i = 1; i + m - 1 < n; i++) {
        // Scoatem s[i-1], adăugăm s[i+m-1]
        hashS = (hashS - s[i - 1] * power % MOD + MOD * MOD) % MOD;
        hashS = (hashS * B + s[i + m - 1]) % MOD;

        if (hashS == hashP) {
            bool match = true;
            for (int k = 0; k < m; k++)
                if (s[i + k] != p[k]) { match = false; break; }
            if (match) fout << i << " ";
        }
    }

    return 0;
}

date.in:

abcabcabd
abc

date.out:

0 3

De ce + MOD * MOD?

La scăderea hashS - s[i-1] * power, rezultatul poate deveni negativ în C++ din cauza aritmeticii modulare.

Adăugăm MOD * MOD pentru a garanta că valoarea e pozitivă înainte de % MOD:

hashS = (hashS - s[i - 1] * power % MOD + MOD * MOD) % MOD;

De ce verificăm caracter cu caracter?

Două șiruri diferite pot avea același hash - acest fenomen se numește coliziune.

Dacă hash-urile sunt egale, verificăm și caracter cu caracter pentru certitudine. În practică, coliziunile sunt rare dacă alegem bine B și MOD.

Pentru siguranță maximă, folosim două hash-uri (două perechi B, MOD) și comparăm ambele. Probabilitatea unei coliziuni duble e extrem de mică.

Complexitate

Timp Memorie
Naive O(n * m) O(1)
Rabin-Karp O(n + m) mediu O(1)
KMP O(n + m) garantat O(m)

În cazul cel mai rău (multe coliziuni), Rabin-Karp poate degrada la O(n*m). În practică, e rapid.

Pas cu pas pentru s = "abcabc", p = "abc", m = 3, B = 131

Hash-ul lui p

hashP = 'a'*B² + 'b'*B + 'c' = 97*131² + 98*131 + 99 = ... (mod 10^9+7)

Prima fereastră din s: “abc”

Același cod ca pentru p → hashS = hashP. Match la poziția 0!

Glisare 1: fereastra devine “bca”

  • Scoatem 'a' (poziția 0): hashS -= 'a' * B²
  • hashS *= B
  • Adăugăm 'a' (poziția 3): hashS += 'a'

hashS = hash-ul pentru “bca”, diferit de hashP.

Glisare 2: fereastra devine “cab”

Diferit de “abc”. Nu match.

Glisare 3: fereastra devine “abc”

  • Scoatem 'c', adăugăm 'c'. hashS == hashP. Match la poziția 3!

Rolling hash - aplicații

Rabin-Karp se bazează pe rolling hash (hash care se actualizează când fereastra se mișcă). Acesta e util și în alte probleme:

1. Găsirea celui mai lung subșir comun între două șiruri

2. Verificarea dacă două subșiruri sunt egale în O(1)

Precalculăm hash-urile prefixelor: - h[i] = hash-ul lui s[0..i-1]

Atunci hash-ul lui s[l..r] poate fi calculat în O(1) din h[r+1] și h[l].

3. Găsirea palindroamelor

Un palindrom are hash-ul normal = hash-ul inversului. Combinăm cu binary search pentru palindromul maxim centrat într-un punct.

Alegerea lui B și MOD

Combinații bune: - B = 31, MOD = 10^9 + 7 - pentru șiruri cu litere mici - B = 131, MOD = 10^9 + 7 - pentru orice caractere - B = 53, MOD = 10^9 + 9 - alternativ

Pentru siguranță, folosește long long pentru hash-uri și MOD prim.

Rabin-Karp vs KMP

Rabin-Karp KMP
Idee Hashing Prefix function
Garantat O(n+m) Nu (coliziuni) Da
Multiple șabloane Ușor (hash-uri în set) Greu
Implementare Mai simplă Mai complexă

KMP e garantat rapid, dar Rabin-Karp e mai flexibil pentru probleme complexe.

Greșeli frecvente

1. Hash negativ

// GRESIT - poate fi negativ
hashS = (hashS - s[i] * power) % MOD;

// CORECT
hashS = (hashS - s[i] * power % MOD + MOD * MOD) % MOD;

2. Lipsa verificării caracter cu caracter

if (hashS == hashP)
    fout << i;  // PERICOL - coliziune!

Mereu verifică pentru a evita coliziunile.

3. B prea mic sau non-prim

B = 10 sau B = 2 produc multe coliziuni. Folosește numere prime medii (31, 131, 37).

4. Overflow la long long

long long a = ..., b = ...;
long long c = a * b;  // POATE DEPĂȘI long long dacă a, b mari!
long long c = a * b % MOD;  // mai bine - aplicăm mod

Ce să reții

  • Rabin-Karp caută un subșir într-un text folosind hashing.
  • Hash polinomial: s[0]*B^(m-1) + s[1]*B^(m-2) + ... + s[m-1].
  • Fereastra se actualizează incremental: O(1) per pas.
  • La egalitate de hash, verificăm caracter cu caracter pentru siguranță (coliziuni).
  • Complexitate medie: O(n + m).
  • Folosim B prim (31, 131) și MOD prim (10^9 + 7).
  • Baza pentru multe tehnici: rolling hash, hash pe prefixe, palindroame.
Cuprins Inapoi Inainte