String-ийг нэг тоо болгож, хоёр string-ийг үсэг үсгээр нь биш, ганц тоогоор харьцуулдаг арга.

Advanced & LegendХугацаа: O(n + m)Санах ой: O(n)
HackerRank дээр бодох

Эхлээд жижиг бодлого

s = "abab" дотор p = "ab" хэдэн удаа байгааг hash-аар тоолъё. a = 1, b = 2 тул hp = 1·31 + 2 = 33.

Урт нь 2 гурван хэсгийн hash: "ab" = 33, "ba" = 2·31 + 1 = 63, "ab" = 33. Эдгээрийн хоёр нь hp-тэй тэнцүү тул хариу 2.

Энгийн аргаас санаа руу

Энгийн арга бол байрлал бүрт p-г үсэг үсгээр нь харьцуулах: O(n · m). Олон хэсгийг хооронд нь олон удаа харьцуулдаг бодлогод энэ нь бүр удаан.

Hashing string бүрийг нэг тоо болгодог. Prefix hash h[]-г нэг удаа бодчихвол дурын хэсгийн hash-ийг O(1)-д олно. Хоёр хэсгийг харьцуулах нь хоёр тоог харьцуулах болж хувирна.

Нэр томьёо ба тэмдэглэгээ

B, M
Суурь ба модуль. Кодонд B = 31, M = 1000003. Тэмцээнд M-ийг 10⁹ + 7 шиг том авна.
hp
p-гийн hash.
h[i]
s-ийн эхний i үсгийн hash. h[0] = 0.
pw[i]
Bⁱ mod M. Хэсгийн hash бодоход хэрэгтэй.
collision
Хоёр өөр string ижил hash-тай болох. Ховор ч боломжтой.
i012345s
b
a
n
a
n
a
код
2
1
14
1
14
1
h

Үсэг бүр тоо болно: a = 1, b = 2, …, z = 26. String-ийг B = 31 суурьтай тоо мэт уншаад, M = 1000003-т хуваасан үлдэгдлийг авна. Энэ тоог hash гэнэ.

Алхам 1 / 15
Хурд
  • Одоогийн үсэг
  • Шинэ h утга
  • Бодсон h
  • Шалгаж буй хэсэг
  • Томьёонд орох h
  • Олдсон
Слайд 1 / 7

String-ийг тоо болгоно

Хоёр string ижил эсэхийг үсэг үсгээр нь шалгахын оронд string бүрийг нэг тоо болговол ганц харьцуулалт л хийнэ. Ийм тоог hash гэнэ.

string-hashing.cpp
#include <bits/stdc++.h>
using namespace std;
const long long B = 31, M = 1000003;
string s, p;
long long h[100005], pw[100005];
int main() {
cin >> s >> p;
int n = s.size(), m = p.size();
long long hp = 0;
for (int i = 0; i < m; i++) hp = (hp * B + p[i] - 'a' + 1) % M;
pw[0] = 1;
for (int i = 0; i < n; i++) {
h[i + 1] = (h[i] * B + s[i] - 'a' + 1) % M;
pw[i + 1] = pw[i] * B % M;
}
int cnt = 0;
for (int i = 0; i + m <= n; i++) {
long long cur = (h[i + m] - h[i] * pw[m] % M + M) % M;
if (cur == hp) {
cnt++;
}
}
cout << cnt << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Текстэд pattern хэдэн удаа орсныг олох, хоёр хэсэг ижил эсэхийг O(1) хугацаанд шалгана. Prefix hash нь palindrome, давтагдсан хэсэг хайх зэрэг олон бодлогод хэрэг болно.

Яаж ажилладаг вэ?

1. Үсэг бүр тоо болно: a = 1, b = 2, …, z = 26. 2. Pattern p-гийн hash: hp = (hp · B + үсэг) mod M. Энд B = 31, M = 1000003. Тоо нь уншихад амар байхаар M-ийг жижиг авсан. Тэмцээнд M = 10⁹ + 7 гэх мэт том тоо авна. 3. Prefix hash: h[i + 1] = (h[i] · B + s[i]) mod M нь s-ийн эхний i + 1 үсгийн hash. pw[i] = Bⁱ mod M. 4. s[i..i + m − 1] хэсгийн hash = (h[i + m] − h[i] · pw[m]) mod M. Энэ нь hp-тэй тэнцвэл pattern олдлоо. Оролт: эхний мөрөнд текст s, дараагийн мөрөнд pattern p (жижиг латин үсэг).

Яагаад зөв, хэр хурдан бэ?

h[i + m] нь h[i]-г pw[m]-ээр үржүүлээд, i-гаас эхэлсэн m урттай хэсгийн hash-ийг нэмсэнтэй тэнцүү. Тиймээс h[i + m] − h[i] · pw[m] нь яг тэр хэсгийн hash. Хасалт сөрөг гарч болох тул + M нэмээд дахин % M авна.

Prefix hash O(n), хэсэг бүр O(1) тул нийт O(n + m). Hash тэнцүү бол string ижил гэж үздэг нь магадлалын таамаг: M ≈ 10⁶ бол санамсаргүй хоёр string сая удаад нэг орчим давхцана. M ≈ 10⁹ эсвэл хоёр модуль ашиглавал бараг алдахгүй.

Түгээмэл алдаа

  • a = 0 гэж кодлох. Тэгвэл "a", "aa", "aaa" бүгд 0 hash-тай болно. Үсгийг 1-ээс эхэлж кодло.
  • Хасалтын дараа + M нэмэхгүй байх. C++-д сөрөг тооны % сөрөг гарна.
  • h[i] * pw[m] int-ээс хэтрэх. M ≈ 10⁹ бол үржвэр 10¹⁸ хүрнэ, long long хэрэгтэй.
  • Жижиг M ашиглах. Олон хэсэг харьцуулах бодлогод collision гарч, хариу буруу болно.

Хязгаарын тохиолдол

  • m == n: ганц хэсэг шалгана.
  • p олдохгүй: нэг ч hash тэнцэхгүй, хариу 0.
  • Давхцсан олдоц ("aaa" дотор "aa"): байрлал бүрийг тусад нь шалгадаг тул бүгдийг тоолно.

Өөрийгөө шалга

  1. B = 31 бол "ba" string-ийн hash хэд вэ?

    Хариу харах

    2·31 + 1 = 63.

  2. "cab" string-ийн hash хэд вэ?

    Хариу харах

    3·31² + 1·31 + 2 = 2916.

  3. Яагаад үсгийг 0-ээс биш 1-ээс кодлодог вэ?

    Хариу харах

    0-ээс кодловол "a", "aa" хоёулаа 0 hash-тай болж ялгагдахгүй.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1."abc" string-ийн hash-ийг B = 31 үед гараар бод.

    Hint харах

    ((1·31) + 2)·31 + 3.

    Хариу ба тайлбар

    1·961 + 2·31 + 3 = 1026.

  2. 2.s[a..a + len − 1] ба s[b..b + len − 1] хоёр хэсэг ижил эсэхийг O(1)-д шалгадаг function бич.

    Hint харах

    Хэсгийн hash-ийн томьёог хоёр удаа хэрэглэ.

    Хариу ба тайлбар

    get(i, len) = (h[i + len] - h[i] * pw[len] % M + M) % M гэж тодорхойлоод get(a, len) == get(b, len) эсэхийг буцаана.

  3. 3.String-д урт нь m ялгаатай хэсэг хэд байгааг ол.

    Hint харах

    Хэсэг бүрийн hash-ийг set эсвэл эрэмбэлсэн array-д хийгээд ялгаатайг нь тоол.

    Хариу ба тайлбар

    Бүх i-д get(i, m)-ийг set<long long>-д хийнэ. Хариу нь set-ийн хэмжээ. O(n log n).

Жишээ

Оролт

banana
ana

Гаралт

2

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.