Wstęp do programowania w C++

Algorytm hashowania

Wstęp

Każdy z nas umie określić, czy dwie liczby są równe. Nietrudno się domyślić, że podobna umiejętność jest przydatna także w przypadku tekstów. Na dzisiejszej lekcji poznasz metodę haszowania. Jej zaletą jest stosunkowo łatwa implementacja i efektywność działania. Posiada również pewną wadę, ale o tym później.

Nieoptymalny sposób porównywania dwóch słów

Na początku spróbujmy rozwiązać prostszy problem. Mając dane dwa słowa W i S, chcielibyśmy sprawdzić, czy podsłowa [i; j]W i [k; l]S są takie same.

• abacababca i bcabaccabc (zaznaczone przedziały nie są takie same)
• aacbbaacab i cabbbaaccc (zaznaczone przedziały są takie same)

Fakt 1: Słowa są równe, gdy literki na odpowiednich pozycjach są takie same. Innymi słowy, jeśli zachodzi:

• W[i] = S[k], W[i + 1] = S[k + 1]... W[j] = S[l]

to słowa są równe. W przeciwnym wypadku się różnią. Załóżmy, że S i W mają długość n (1 ≤ n ≤ 10^6). Porównywanie kolejnych literek zajmuje O(k − l + 1), czyli w najgorszym wypadku O(n) czasu. Co gdybyśmy chcieli porównać w ten sposób q (1 ≤ q ≤ 10^6) różnych par podsłów? Odbyłoby się to w czasie O(qn), czyli w najgorszym wypadku O(10^6 ⋅ 10^6) = O(10^12). Jeśli nie chcemy czekać kilku lat na wynik i nie mamy superkomputera, musimy wymyślić lepszą metodę.

bool same = true;
for (int i = 0; i < length; i++) {
    if (w1[i] != w2[i]) same = false;
}
return same;

W poszukiwaniu szybkości

Spróbujmy wymyślić inny, szybszy sposób porównywania słów. Tak jak wcześniej zauważyłem, umiemy porównywać liczby. Wykorzystajmy to! Stwórzmy taką funkcję F(si), gdzie si jest słowem, że: F(s1) = F(s2), gdy s1 = s2 oraz F(s1) ≠ F(s2), gdy s1 ≠ s2. Na początku zamieńmy pojedyncze litery na liczby; każdą na numer jej pozycji w alfabecie (a na 1, b na 2, c na 3 itd.). Od teraz pisząc „litera”, będę miał na myśli odpowiadającą jej wartość.

Pierwszym pomysłem, na jaki możemy wpaść, jest F sumujące litery w słowie. Zauważmy, że jest to beznadziejne rozwiązanie, które bardzo często nie spełnia drugiego założenia F. Na przykład dla słów abcbbd i abcdbb mamy:

• F(abcbbd) = 1 + 2 + 3 + 2 + 2 + 4 = 14
• F(abcdbb) = 1 + 2 + 3 + 4 + 2 + 2 = 14

Wykorzystajmy fakt, że tak naprawdę obchodzi nas tylko, czy litery na tych samych pozycjach są równe. Spróbujmy zatem przemnożyć każdą z liter przez numer jej pozycji w słowie i zsumujmy uzyskane wartości. Brzmi sensowniej od wcześniejszego podejścia i faktycznie działa lepiej. Choćby dla poprzedniego przykładu:

• F(abcbbd) = 1 ⋅ 0 + 2 ⋅ 1 + 3 ⋅ 2 + 4 ⋅ 1 + 5 ⋅ 1 + 6 ⋅ 3 = 35
• F(abcdbb) = 1 ⋅ 0 + 2 ⋅ 1 + 3 ⋅ 2 + 4 ⋅ 3 + 5 ⋅ 1 + 6 ⋅ 1 = 31

więc F(abcbbd) ≠ F(abcdbb).

Niestety takie F dalej nie działa. Na przykład dla słów cb i ac mamy:

• F(cb) = 1 ⋅ 3 + 2 ⋅ 2 = 7
• F(ac) = 1 ⋅ 1 + 2 ⋅ 3 = 7

Haszowanie

Niech p będzie małą liczbą pierwszą, większą od rozmiaru alfabetu. W przypadku alfabetu angielskiego możemy wybrać p = 29 lub p = 31. Zdefiniujmy nasze F jako:

• F(S) = p^0 ⋅ S0 + p^1 ⋅ S1 + ... + p^(n−1) ⋅ Sn−1

gdzie Si oznacza literę na i-tej pozycji. Nie ulega wątpliwości fakt, że dla dwóch takich samych słów - argumentów wartości F będą takie same. Pozostaje pytanie, co z warunkiem:

• F(s1) ≠ F(s2), gdy s1 ≠ s2.

Oczywiście może zdarzyć się przypadek, że nie zostanie on spełniony. Jednakże jest to bardzo mało prawdopodobne. Pozwolę sobie pominąć dowód tego faktu. Musicie uwierzyć mi na słowo :)

Tak policzone F nazwiemy funkcją haszującą, a całą metodę porównywania tekstów haszowaniem.

Kilka spraw praktycznych

1. Na olimpiadach jak i w prawdziwym życiu haszowanie jest wystarczającą i najczęściej używaną metodą porównywania tekstów. Jednakże mogą zdarzyć się pojedyncze przypadki zadań, w których autor układa złośliwe testy. W takiej sytuacji należy napisać dwie różne funkcje haszujące różniące się jedynie liczbą p i za każdym razem wykonywać te same operacje dwa razy. W ten sposób prawdopodobieństwo błędu jest tak niskie, że wygenerowanie testów uwalniających jest praktycznie niemożliwe.
2. Funkcja F bardzo szybko rośnie i już przy niedługich słowach osiąga wartości powyżej zakresów long long’a. Zamiast trzymać wartość F, będziemy trzymać jej resztę z dzielenia przez liczbę pierwszą M rzędu miliarda (np. 10^9 + 696969 czy 10^9 + 7). Z tego powodu:

• F(S) = (p^0 ⋅ S0 + p^1 ⋅ S1 + ... + p^(n−1) ⋅ Sn−1) mod M

Działając na resztach nie możemy wykonywać operacji dzielenia, bo:

• (a mod M) ÷ (b mod M) ≠ (a ÷ b) mod M

oraz musimy uważać przy odejmowaniu. Nawet jeśli b > a, to a mod M może być większe niż b mod M. Oznacza to, że ich różnica może być ujemna, czego byśmy nie chcieli. Dlatego do różnicy dwóch liczb zawsze należy dodać M przed wykonaniem operacji modulo:

• (b − a) mod M = (b mod M − a mod M + M) mod M

3. Musimy umieć obliczać potęgi liczby p. W tym celu zdefiniujmy sobie tablicę Pot, ot tak, że:

• Pot[0] = 1;
• dla i > 0: Pot[i] = (Pot[i - 1] ⋅ p) % M;

Wszystkie potrzebne wartości funkcji Pot możemy obliczyć w następujący sposób:

Pot[0] = 1;
for (int i = 1; i <= n; ++i) {
    Pot[i] = (Pot[i - 1] * p) % M;
}

Kilka ciekawych sztuczek

1. Często będzie potrzebna umiejętność porównywania dwóch podsłów. Zastanówmy się najpierw, jak porównać podsłowo S z podsłowem W zaczynającymi się na tej samej pozycji odpowiednich słów. W tab[i] będziemy trzymać wartość funkcji haszującej dla i-tego prefiksu S. Analogicznie zdefiniujmy tab1[i] dla W. Porównajmy sobie teraz podsłowa [a; b]. Zauważmy, że:

• (tab[j] − tab[i − 1] + M) mod M = (p^i ⋅ F(S[i..j])) mod M
• (tab1[j] − tab1[i − 1] + M) mod M = (p^i ⋅ F(W[i..j])) mod M

Wiedząc, że podsłowa będą równe wtedy i tylko wtedy, gdy zachodzi warunek:

• F(S[i..j]) = F(W[i..j])

wiemy, że wystarczy sprawdzić, czy:

• (tab[j] − tab[i − 1] + M) mod M = (tab1[j] − tab1[i − 1] + M) mod M

2. Bardzo przydatną umiejętnością jest też znajdowanie indeksu pierwszej litery, na której słowa się różnią. Możemy wykorzystać do tego wyszukiwanie binarne po tablicy tab. „Wstrzelmy się” w połowę długości słów i sprawdźmy, czy ich hasze są takie same. Jeżeli tak, to wszystkie literki na tym prefiksie są takie same. Oznacza to, że pierwsza różna pozycja znajduje się na prawo od naszego „strzału”. W przeciwnym wypadku jest gdzieś na tym prefiksie.

Stwórz i zastosuj funkcję skrótu dla ciągu znaków według przedstawionego algorytmu dla (p = 29, M = 1000000007, 'a' = 1, 'b' = 2, ...).

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę zestawów testowych (nie więcej niż 100).

Każdy zestaw składa się z napisu złożonego wyłącznie z małych liter języka łacińskiego nie dłuższy niż 1000 znaków.

Wyjście

Dla każdego wyrazu jedna liczba będąca jego hashem.

Przykład

Wejście:
5
adam
alina
fraktal
alamakota
alamakot


Wyjście:
318015
1056645
172806220
392931145
146521684