Текстээр гулсах цонх бүрийн hash-ийг хурдан шинэчилж, хайх string-тэй тоогоор нь харьцуулдаг хайлт.

IntermediateХугацаа: O(n + m)Санах ой: O(1)

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

s = "abab" текстээс p = "ab"-г хайя. a = 1, b = 2 гэвэл p-ийн hash 1·31 + 2 = 33.

2 тэмдэгттэй цонх гурав бий: "ab" = 33, "ba" = 2·31 + 1 = 63, "ab" = 33. Hash нь 33-тай тэнцүү хоёр цонхыг шалгахад хоёулаа "ab". Хариу 2.

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

Энгийн арга: байрлал бүрт p-г тэмдэгт тэмдэгтээр харьцуулна. Хамгийн муудаа n · m үйлдэл. n = 100 000, m = 1000 бол 100 сая.

Гол санаа: цонх бүрийг нэг тоо (hash) болгоно. Тоо харьцуулах нэг л үйлдэл. Цонх нэг алхам гулсахад hash-ийг эхнээс нь бодохгүй: гарсан тэмдэгтийг хасаад, 31-ээр үржүүлж, шинэ тэмдэгтийг нэмнэ. Hash таарсан үед л тэмдэгтүүдийг шалгана.

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

hash
String-ийг 31-ийн суурьтай тоо шиг уншсан утга. "abc" → 1·31² + 2·31 + 3 = 1026.
hp, cur
hp нь p-ийн hash, cur нь одоогийн цонхны hash.
pw
31^(m - 1) % M. Цонхны хамгийн зүүн тэмдэгтийн "жин".
M = 10⁹ + 7
Тоо хэт томрохгүйн тулд бүх үйлдлийг M-д хуваасан үлдэгдлээр хийнэ.
collision
Өөр хоёр string ижил hash гаргах. Тиймээс hash таарахад тэмдэгтүүдийг шалгадаг.
i012345678910s
a
b
r
a
c
a
d
a
b
r
a
код
1
2
18
1
3
1
4
1
2
18
1
p

Текст: "abracadabra", хайх string: "abra". Тэмдэгт бүрийг тоо болгоно: a = 1, b = 2, c = 3… p болон 4 тэмдэгттэй цонх бүрийг 31-ийн суурьтай нэг тоо болгож харьцуулна.

Алхам 1 / 21
Хурд
  • Одоогийн цонх
  • Цонхонд орж ирсэн тэмдэгт
  • Цонхноос гарсан тэмдэгт
  • Хайх string p
  • Олдсон
Слайд 1 / 6

Цонх гулсуулж хайна

Текстийн 4 тэмдэгттэй хэсэг бүрийг цонх гэж нэрлэе. Цонх бүрийг p-тэй тэмдэгт тэмдэгтээр нь харьцуулбал удаан. Цонх бүрийг нэг тоо болговол ганцхан харьцуулалт хийнэ.

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

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

Текстээс p-г хайхдаа цонх бүрийг тэмдэгт тэмдэгтээр биш, ганц тоогоор харьцуулах. Олон string-ийг зэрэг хайх, давтагдсан хэсэг олоход тохиромжтой.

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

1. Тэмдэгт бүрийг тоо болгоно: a = 1, b = 2, … p-г 31-ийн суурьтай тоо шиг уншиж hp-г олно. 2. Текстийн эхний m тэмдэгттэй цонхны hash-ийг cur гэж олно. 3. cur = hp бол тэмдэгтүүдийг нь шалгаж, ижил бол тоолно. 4. Цонхыг гулсуулахдаа гарсан тэмдэгтийн хувийг (код · 31^(m − 1)) хасаад, 31-ээр үржүүлж, орж ирсэн тэмдэгтийг нэмнэ. Тоо хэт томрохгүйн тулд M = 10⁹ + 7-д хуваасан үлдэгдлийг хадгална. Оролт: эхний мөрөнд текст, дараагийн мөрөнд p. Гаралт: p хэдэн удаа олдсон.

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

Ижил string-ийн hash үргэлж ижил. Тиймээс p-тэй таарах цонх бүрийн hash hp-тэй тэнцүү байна, нэг ч олдвор алдагдахгүй. Hash таарсан цонхыг тэмдэгт бүрээр нь дахин шалгадаг тул илүү олдвор ч тоологдохгүй.

Эхний hash-ийг бодоход O(m), цонх бүрийг шинэчлэхэд O(1). Collision ховор тул шалгалт цөөхөн хийгдэнэ. Дунджаар O(n + m). n = 1 000 000 бол сая орчим алхам.

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

  • Гулсуулахдаа + M нэмэхээ мартах. cur - x сөрөг гарч болох бөгөөд C++-д сөрөг тооны % сөрөг үлдэгдэл өгнө.
  • (s[i] - 'a' + 1) * pw үржвэрийг int-д бодох. pw нь 10⁹ хүртэл тул long long хэрэгтэй.
  • a = 0 гэж кодлох. Тэгвэл "a", "aa", "aaa" бүгд 0 hash-тэй болж олон collision гарна. a = 1-ээс эхэл.
  • Hash таарсан даруйд олдсон гэж тоолох. Collision гарвал буруу хариу гарна.

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

  • p текстээс урт: цонх огт байхгүй, хариу 0.
  • p текстэй ижил урттай: ганц цонх шалгана.
  • Давхцаж гарах олдвор, s = "aaaaa", p = "aa": цонх бүр таарна, хариу 4.

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

  1. "ba" string-ийн hash хэд вэ?

    Хариу харах

    2·31 + 1 = 63.

  2. n = 11, m = 4 бол хэдэн цонх шалгах вэ?

    Хариу харах

    n - m + 1 = 8 цонх.

  3. Hash таарсны дараа яагаад тэмдэгтүүдийг дахин шалгадаг вэ?

    Хариу харах

    Өөр string санамсаргүй ижил hash гаргаж болно. Шалгалт хийснээр хариу үргэлж зөв.

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

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

  1. 1."abc" цонхны hash-ээс "bcd" цонхны hash-ийг гулсуулах аргаар ол.

    Hint харах

    "abc" = 1026. Гарах a тэмдэгтийн жин 1·31² = 961.

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

    (1026 - 961) · 31 + 4 = 2019. Шууд бодоход 2·961 + 3·31 + 4 = 2019, таарч байна.

  2. 2.Кодыг олдсон байрлал бүрийг хэвлэдэг болго.

    Hint харах

    cnt++ хийдэг мөрийн хажууд i-г хэвлэ.

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

    if (cur == hp && s.substr(i, m) == p) { cnt++; cout << i << ' '; }. "abracadabra" дотроос "abra" хайхад 0 7 хэвлэнэ.

  3. 3.String-д хоёр удаа гарч байгаа L урттай хэсэг байгаа эсэхийг шалга.

    Hint харах

    L урттай цонх бүрийн hash-ийг set-д хийгээд, давхардсан эсэхийг хар.

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

    Цонх гулсуулж, hash бүрийг set<long long>-д нэмнэ. Hash аль хэдийн байвал тэмдэгтүүдийг шалгаад тийм гэж хариулна. Хугацаа O(n log n). Хамгийн урт давтагдах хэсгийг L-ээр Binary Search хийж олж болно.

Жишээ

Оролт

abracadabra
abra

Гаралт

2