Dərs 2: String Hashing

Kontekst

Sətirlərin və sözlərin bir-birinə bərabər olmasını yoxlamaq bizə bəzən lazım olur. Məsələn, sözün palindrom olmağını yoxlamaq üçün, onun tərsinə bərabər olub-olmadığını yoxlayırıq. Yaxud bizə bir milyon uzun söz verilsə, bir sözün orada rast gəlib-gəlməməsini yoxlamaq çətinləşir. Adi halda bu halı necə həll edərik?

Sətir kodlaması (hashing) elə bir metoddur ki, biz sözləri riyazi funksiya ilə kodlaşdırıb ədəd kimi başa düşə bilək. Bu alqoritmin istifadəsi olimpiadalarda o qədər də çox düşmür, amma məncə öyrənilməsi çox vacibdir, çünki gündəlik istifadə etdiyimiz başqa strukturları anlamağa yardım edir. Əlavə olaraq, bəzi məsələlərin nəzərdə tutulmuş həlli başqa olsa da, hashing ilə gözlənilməz və maraqlı həllər də ola bilir. Özünüz görəcəksiniz ki, bu metodu yalnız sətirlərə yox, hətta massivlərə də tətbiq etmək olar. Gəlin alqoritmə keçək.

İzah

Onluq sistemdə ədədləri necə yazdığımızı yadımıza salaq: $$16428 = 1 \cdot 10^4 + 6 \cdot 10^3 + 4 \cdot 10^2 + 2 \cdot 10^1 + 8 \cdot 10^0$$

Əslində, sözləri də say sistemində düşünmək olar. Məsələn, $a=1$, $b=2$, $c=3$ kimi say sistemi qursaq, $$abc = 1 \cdot 10^2 + 2 \cdot 10^1 + 3 \cdot 10^0 = 123$$ kimi yaza bilərdik. Nəzərə alın ki, burada 10-un qüvvətlərinə vururuq və hərflərimizin sayı 3 ədəd olduğu üçün heç bir kəsişmə olmur. Amma 10 əvəzinə 2-nin qüvvətlərinə vursaq idik, onda kəsişmə ola bilərdi. Məsələn, $abc = 1 \cdot 2^2 + 2 \cdot 2^1 + 3 \cdot 2^0 = 7$ və $ca = 3\cdot 2^1 + 1 = 7$ eyni ədədə uyğun gəlir (bizə 7 desələr, onun hansı söz olduğunu tapa bilmərik). Vurduğumuz qüvvət fərqli hərflərin sayından çox olmalıdır ki, qarşılıqlı birəbir funksiya ala bilək.

Məsələn, kiçik latın hərfləri ilə işləsəydik, onda 26-lıq say sistemində (orada $a=0, b=1, \dots$ və sair) bütün sözləri göstərmək olardı. Amma onda $zz\dots z$ (14 ədəd z hərfi) sözünün hansı ədədə uyğun gəldiyinə baxaq: $$zzz\dots z = \sum_{i=0}^{13} 25\cdot 26^i = 64509974703297150975 > 10^{19}$$ Bu ədədi biz C++-da standart tiplərlə ifadə edə bilmirik. Başqa cür ifadə etsək belə, 19 dənə rəqəmi yaddaşda saxlamaq 14 hərfi saxlamaqdan az sürət tələb etməyəcək. Deməli, bizim üçün 26-lıq say sistemi ümumi halda uyğun deyil, xüsusən də böyük sözlər üçün (əgər sözlər çox kiçik olsa idi, işlətmək olardı).

Bu problemdən çıxış yolumuz isə çox da çətin deyil: gəlin kəsişmələr ilə razı olaq. Elə funksiya seçək ki, orada həqiqətən də, bayaqkı kimi iki söz eyni ədədə bərabər ola bilsin, amma bu kəsişmələr çox nadir baş verəcək. Sadə $p$ və $M$ ədədləri seçək, $M$ isə böyük olsun. Məsələn, $p=47, M=1000000007$. Sonra isə $a=1, b=2, \cdots z=26$ uyğunlamasından istifadə edək. Kodlama funksiyamız ilə belə olsun: $$hash(s) = \sum_{i=0}^{|s|-1} s_i \cdot p^i \mod M$$ Məsələn, $$hash(``abc") = 1 \cdot 47^0 + 2 \cdot 47^1 + 3 \cdot 47^2 \mod 1000000007 = 6722$$ Bu metod ilə kodlaması kəsişən iki söz tapmaq çətindir. Riyazi baxsaq, iki təsadüfi sözün kodlamasının eyni olması ehtimalı $\frac{1}{M}$, bizim halda milyardda bir olur. Amma sözlərin sayı artdıqca, bu ehtimal da artır. $n$ söz və $M$ kodlama namizədi (yəni, neçə fərqli kodlama var) olsa, onda orada ən azı iki sözün kəsişmə ehtimalı təxminən $1 - e^{-\frac{n^2}{2M}}$ olur. Bunu əzbərdən bilməyə ehtiyac yoxdur, amma haqqında daha aşağıda danışırıq.

İndi belə bir məsələyə baxaq. Bizə $n$ söz verilir, hərəsinin uzunluğu $m$-ə bərabərdir. Onların arasında neçə fərqli söz var? Ağlımıza bir neçə sadə həll gələ bilər. Məsələn, bütün sözləri set strukturuna qoymaq və sonra onun uzunluğunu tapmaq. Yaxud bu sözləri sort edib ardıcıl gələn sözləri yoxlamaq. Bu iki həllin də zaman çətinliyi $O(nm\log n)$ olur. Çünki $n$ söz var və biz onları sort edəndə yaxud set strukturuna daxil edəndə onlar arasında müqayisələr edirik. Bizim halda isə müqayisələr üçün $O(m)$ vaxt lazımdır. Biz isə daha yaxşı həll yaza bilərik. Sözlərin hash dəyərini tapaq, sonra isə məsələni ədədlər üzərində həll edək. Hər bir sözün kodlanmış dəyərini tapmaq üçün $O(m)$ vaxt lazımdır. Onda ümumi zaman $O(nm + n\log n)$ olur. Məsələdə $n=10^6$ və $m=20$ olsa idi, daha adi sort ilə olan həll zaman limitini keçməyə bilərdi.

#pragma GCC optimize("O3")
#include <iostream>

using namespace std;

int get_hash(const string &s) {
  const int p = 43;
  const int m = 1e9 + 7;

  int h = 0, pow = 1;
  for (char c : s) {
    h = (h + 1LL * (c - 'a' + 1) * pow % m) % m;
    pow = 1LL * pow * p % m;
  }
  return h;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    h[i] = get_hash(s[i]);
  }
  sort(h.begin(), h.end());
  int ans = 1;
  for (int i = 1; i < n; i++) {
    if (h[i] != h[i - 1]) {
      ans++;
    }
  }
  cout < ans < '\n';
  return 0;
}

Belə bir nüansa da baxaq. Bizə bir milyon söz verilib. Bu sözlər arasında ən azı iki təsadüfi sözün olma ehtimalı necədir? Bizim halda $M \approx 10^9$ olduğundan: $$1 - e^{-\frac{(10^6)^2}{2\cdot 10^9}} = 1 - e^{-500} \approx 1$$ olur. Bu isə kodumuzun səhv işləyə biləcəyi mənasına gəlir (məsələnin testlərindən asılıdır, çox vaxt bəxtimiz gətirə də bilir). Xoşbəxtlikdən, bundan qurtulmağın da asan yolu var: kodlama üçün iki fərqli funksiya götürürük. Məsələn, bayaq $p=47, M=10^9+7$ götürmüşdük, əlavə olaraq da, $p'=29, M'=10^9+7$ götürək və hər iki funksiyanın nəticəsini yoxlayaq. Onda kodlama üçün fərqli namizədlərin sayı təxminən $10^{18}$ olur. Yuxarıdakı hesablamada $M=10^{18}$ götürsək, o zaman ehtimal $0.0000005$ olur (iki-milyonda bir). Bu, yetəri qədər yaxşıdır. Qısaca, bunu nəzərə alın: söz sayı 10000-dən çox olsa, onda kodlama üçün iki fərqli funksiya götürmək lazımdır.

Dərsdə həll
Password (Div.1 B) məsələsini həll et.

Dərsdə həll
Palindromic Partitions (CEOI 2017) məsələsini həll et.

Kömək üçün check_equal funksiyasına baxa bilərsiniz:

const int N = 1e6 + 5;
const int P = 43;
const int M = 1e9 + 7;

int n;
int p[N], h[N];

// s[a..a+l-1] == s[b..b+l-1]
bool check_equal(int a, int b, int l) {
  int ha = (h[a + l - 1] - h[a - 1] + M) % M;
  int hb = (h[b + l - 1] - h[b - 1] + M) % M;
  return 1ll * ha * p[b - a] % M == hb;
}

int main() {
  string s;
  cin >> s;
  n = s.size();

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

  h[0] = 0;
  for (int i = 1; i <= n; i++) {
    h[i] = (h[i - 1] + 1LL * (s[i - 1] - 'a' + 1) * p[i - 1] % M) % M;
  }
}

Əlavə faydalı resurslar

• CSES Kitabında String Hashing
• USACO Guide Gold: String Hashing
• CP-Algorithms: String Hashing