Текстээс pattern хайхдаа таарсан хэсгээ санаж, текстэд хэзээ ч ухрахгүй хурдан арга.

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

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

Текст s = "abababa" дотор p = "aba" хэдэн удаа орсныг тоолъё. Index 0, 2, 4-өөс эхэлсэн гурван хэсэг таарна, тиймээс хариу 3. Давхцсан хэсгүүдийг ч тоолно.

p-гийн pi хүснэгт нь [0, 0, 1]. "aba" олдсоны дараа сүүлийн "a" нь дараагийн олдоцын эхлэл болно. KMP үүнийг pi хүснэгтээс мэдэж, текстэд ухрахгүй.

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

Энгийн арга бол текстийн байрлал бүрээс p-г үсэг үсгээр нь тулгах. Хамгийн муудаа O(n · m): s = "aaaa…a", p = "aa…ab" бол байрлал бүрт бараг бүтэн p-г шалгана.

KMP таарсан хэсгийг хаядаггүй. k үсэг таараад дараагийнх нь таарахгүй бол таарсан хэсгийн төгсгөл нь p-гийн эхлэлтэй хэр давхцахыг pi хүснэгт хэлж өгнө. Тиймээс k-г pi[k − 1] болгоод үргэлжлүүлнэ, i хэзээ ч ухрахгүй.

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

prefix, suffix
String-ийн эхний хэсэг ба сүүлийн хэсэг. "abcab"-д "ab" нь prefix ч, suffix ч мөн.
pi[i]
p[0..i] хэсгийн өөрөөсөө богино prefix ба suffix хамгийн ихдээ хэдэн үсгээр давхцах вэ.
k
Одоогоор p-гийн эхний хэдэн үсэг таарч байгаа.
cnt
p текстэд хэдэн удаа олдсон.
012345678s
a
b
c
a
b
c
a
b
d
p
a
b
c
a
b
d
pi
0

Текст: "abcabcabd", pattern: "abcabd". Эхлээд p-гийн pi хүснэгтийг бөглөнө. Үсэг таарахгүй үед хаашаа үсрэхийг энэ хүснэгт хэлж өгнө.

Алхам 1 / 19
Хурд
  • Харьцуулж буй үсэг
  • Таарсан хэсэг
  • Ашиглах pi утга
  • Шинэ pi утга
  • Олдсон pattern
  • Одоохондоо хэрэглэхгүй
Слайд 1 / 7

Текстээс pattern хайх

Текстээс pattern хайхдаа үсэг таарахгүй болгонд дахин эхнээс нь эхэлбэл удаан. KMP аль хэдийн таарсан хэсгээ санаж, текстэд хэзээ ч ухрахгүй.

kmp.cpp
#include <bits/stdc++.h>
using namespace std;
string s, p;
int pi[100005];
int main() {
cin >> s >> p;
int n = s.size(), m = p.size();
for (int i = 1; i < m; i++) {
int k = pi[i - 1];
while (k > 0 && p[i] != p[k]) {
k = pi[k - 1];
}
if (p[i] == p[k]) {
k++;
}
pi[i] = k;
}
int k = 0, cnt = 0;
for (int i = 0; i < n; i++) {
while (k > 0 && s[i] != p[k]) {
k = pi[k - 1];
}
if (s[i] == p[k]) {
k++;
}
if (k == m) {
cnt++;
k = pi[k - 1];
}
}
cout << cnt << '\n';
return 0;
}

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

Урт текстэд pattern хэдэн удаа орсныг O(n + m) хугацаанд олно. pi хүснэгт (prefix function) нь string-ийн олон бодлогын түлхүүр.

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

1. Pattern p-гийн pi хүснэгтийг бөглөнө: pi[i] нь p[0..i] хэсгийн prefix ба suffix хамгийн ихдээ хэдэн үсгээр давхцахыг заана. Хэсэг өөрөө тооцогдохгүй. 2. Текстийг зүүнээс баруун тийш ганц удаа уншина. k нь p-гийн хэдэн үсэг таарч байгааг заана. 3. Үсэг таарвал k нэгээр өснө. Таарахгүй бол k = pi[k − 1] болгож, арай богино prefix-ээс үргэлжлүүлнэ. 4. k нь p-гийн урттай тэнцвэл pattern олдлоо: cnt-ыг нэгээр нэмнэ. Оролт: эхний мөрөнд текст s, дараагийн мөрөнд pattern p (жижиг латин үсэг).

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

Текстийн i байрлалд k нь текстийн i хүртэлх хэсгийн төгсгөлтэй давхцах p-гийн хамгийн урт prefix-ийн урт. Үсэг таарахгүй бол дараагийн боломжит урт нь pi[k − 1], учир нь таарсан k үсгийн аль ч урт suffix p-гийн prefix биш. Тиймээс ямар ч олдоцыг алгасахгүй.

Нэг i алхамд k ихдээ 1-ээр өсдөг. While loop бүр k-г багасгадаг тул нийт багасалт нийт өсөлтөөс хэтрэхгүй. Иймээс текстийн хэсэг O(n), pi хүснэгт O(m), нийт O(n + m). n = 10⁶ бол хэдхэн сая үйлдэл.

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

  • while биш if бичих. Нэг удаа үсрээд л зогсвол дараагийн богино prefix-ийг шалгахгүй, олдоц алдагдана.
  • p олдсоны дараа k = pi[k − 1] болгохоо мартах. Дараагийн алхамд p[m] гэж array-гээс гарна.
  • pi хүснэгтийг i = 0-ээс эхлэн бөглөх. pi[0] үргэлж 0, loop i = 1-ээс эхэлнэ.
  • Давхцсан олдоцыг тоолохгүй гэж бодох. Энэ код "aaaaa" дотор "aa"-г 4 удаа олно.

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

  • p нь s-тэй ижил урттай: олдвол хариу 1, үгүй бол 0.
  • p-гийн бүх үсэг ижил, жишээ нь "aaa": pi нь [0, 1, 2], олдоц бүрийн дараа k = 2 болж давхцсан олдоцыг шууд олно.
  • p текстэд огт байхгүй: cnt 0 хэвээр үлдэнэ.
  • m = 1: pi хүснэгт нь ганц 0, алгоритм зүгээр л тэр үсгийг тоолно.

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

  1. p = "aaaa" бол pi хүснэгт юу вэ?

    Хариу харах

    [0, 1, 2, 3].

  2. p = "abcab" бол pi хүснэгт юу вэ?

    Хариу харах

    [0, 0, 0, 1, 2].

  3. s = "aaaaa", p = "aa" бол хариу хэд вэ?

    Хариу харах

    4. Index 0, 1, 2, 3-аас эхэлсэн олдоцууд.

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

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

  1. 1.p = "ababaca" бол pi хүснэгтийг гараар бөглө.

    Hint харах

    Үсэг бүрт: өмнөх k-гаас эхэлж, таарахгүй бол k = pi[k − 1].

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

    [0, 0, 1, 2, 3, 0, 1].

  2. 2.Тоолохын оронд p олдсон бүх эхлэлийн index-ийг хэвлэдэг болго.

    Hint харах

    k == m болох үед i нь олдоцын хаана байна вэ?

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

    cnt++-ийн оронд cout << i - m + 1 << " ";. "abababa", "aba" дээр 0 2 4 хэвлэнэ.

  3. 3.String-ийн хамгийн богино period-ийг ол. Жишээ нь "abcabcabc" дотор "abc" давтагддаг тул period нь 3.

    Hint харах

    Зөвхөн pi хүснэгтийн сүүлийн утга хэрэгтэй.

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

    n - pi[n - 1]. "abcabcabc" бол pi хүснэгтийн сүүлийн утга 6 тул 9 − 6 = 3. Хэрэв n нь энэ period-д хуваагдвал string бүтэн давталтаас тогтоно.

Жишээ

Оролт

abcabcabd
abcabd

Гаралт

1

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

Бодлого

Хичээл

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