String-ийн байрлал бүрээс эхэлсэн хэсэг string-ийн эхлэлтэй хэдэн тэмдэгтээр ижил болохыг бүгдийг нь O(n) хугацаанд олдог арга.

Advanced & LegendХугацаа: O(n)Санах ой: O(n)

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

s = "aabxaab" string өгөгдсөн. Байрлал бүрээс эхэлсэн хэсэг s-ийн эхлэлтэй хэдэн тэмдэгтээр ижил вэ?

4-р байрлалаас эхэлсэн хэсэг нь "aab", s-ийн эхлэл ч "aab". Дараагийн тэмдэгт нь string-ээс гарчихна. Тиймээс z[4] = 3. Бүгдийг нь бичвэл z = [0, 1, 0, 0, 3, 1, 0].

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

Энгийн арга: байрлал бүрээс эхлээд s-ийн эхлэлтэй тэмдэгт тэмдэгтээр харьцуулна. s = "aaaa…a" бол байрлал бүрт бараг n харьцуулалт хийгээд нийт n² болно.

Гол санаа: олсон давхцлаа санана. [l, r] хайрцаг нь s[l..r] хэсэг s-ийн эхлэлтэй ижил гэдгийг хэлдэг. i хайрцаг дотор байвал s-ийн эхэнд i - l байрлалд яг ийм хэсэг бий. Тэндхийн z[i - l] бэлэн тул түүнээс эхэлнэ. Хайрцгаас гарсан хэсгийг л шинээр харьцуулна.

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

z[i]
s-ийн i-р байрлалаас эхэлсэн хэсэг s-ийн эхлэлтэй хэдэн тэмдэгтээр ижил вэ. z[0]-ийг 0 гэж үлдээнэ.
prefix
String-ийн эхлэл. "abc" string-ийн prefix нь "", "a", "ab", "abc".
[l, r]
Одоогоор хамгийн баруун тийш хүрсэн давхцал. s[l..r] нь s-ийн эхний r - l + 1 тэмдэгттэй ижил.
min(r - i + 1, z[i - l])
Хайрцгаас гарахгүйгээр итгэлтэй хэлж болох урт. Үүнээс цааш шалгаагүй тул итгэж болохгүй.
0123456s
a
b
a
c
a
b
a
эхлэлz
–
l = 0r = 0

s = "abacaba". z[i] бүрийг олъё: s-ийн i-р байрлалаас эхэлсэн хэсэг s-ийн эхлэлтэй хэдэн тэмдэгтээр ижил вэ. Шар хайрцаг [l, r] бол одоогоор хамгийн баруун тийш хүрсэн давхцал.

Алхам 1 / 16
Хурд
  • Одоогийн байрлал, харьцуулж буй тэмдэгт
  • Таарсан хэсэг
  • Хайрцаг [l, r]
  • Дахин ашиглах z утга
  • Шинэ z утга
  • Хариу
Слайд 1 / 6

String-ийн эхлэл хаана давтагдах вэ?

z[i] нь s-ийн i-р байрлалаас эхэлсэн хэсэг s-ийн эхлэлтэй хэдэн тэмдэгтээр ижил вэ гэдгийг заана. s = "abacaba" үед эхлэл нь "aba", 4-р байрлалаас эхэлсэн хэсэг нь ч "aba". Тиймээс z[4] = 3.

z-function.cpp
#include <bits/stdc++.h>
using namespace std;
string s;
int z[100005], l, r;
int main() {
cin >> s;
int n = s.size();
for (int i = 1; i < n; i++) {
if (i <= r) {
z[i] = min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
for (int i = 0; i < n; i++) cout << z[i] << ' ';
cout << '\n';
return 0;
}

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

String-ийн эхлэл хаана, хэр урт давтагдаж байгааг мэдэх. p + "#" + s гэж нийлүүлээд текстээс p хайх, string-ийн давтагдах хамгийн богино хэсгийг олох зэрэг олон бодлогод шууд хэрэглэгдэнэ.

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

1. z[i] нь s-ийн i-р байрлалаас эхэлсэн хэсэг s-ийн эхлэлтэй хэдэн тэмдэгтээр ижил вэ гэдгийг заана. z[0]-ийг 0 гэж үлдээнэ. 2. [l, r] хайрцаг бол одоогоор хамгийн баруун тийш хүрсэн давхцал: s[l..r] нь s-ийн эхлэлтэй ижил. 3. i хайрцаг дотор байвал яг ийм хэсэг s-ийн эхэнд i − l байрлалд бий. Тиймээс z[i]-г min(r − i + 1, z[i − l]) гэж шууд эхлүүлнэ. 4. Дараа нь тэмдэгт ижил байх хүртэл z[i]-г нэмнэ. Хайрцгаас хэтэрвэл l = i, r = i + z[i] − 1 болгоно. Оролт: нэг мөрөнд string. Гаралт: z[0] … z[n − 1].

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

s[l..r] нь s-ийн эхлэлтэй ижил. Тиймээс s[i..r] нь s[i - l..r - l]-тэй ижил. Тэр хэсгийн хувьд z[i - l] бэлэн. Гэхдээ r-аас цааш юу байгааг бид хараахан мэдэхгүй тул r - i + 1-ээр хязгаарлана. Үлдсэнийг while loop өөрөө шалгана.

Амжилттай харьцуулалт бүр r-ыг нэгээр баруун тийш түлхдэг. r нь n-ээс хэтрэхгүй тул нийт амжилттай харьцуулалт n орчим. Амжилтгүй харьцуулалт i бүрт нэг л удаа. Хугацаа O(n), санах ой O(n). n = 1 000 000 бол хэдхэн сая үйлдэл.

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

  • Хайрцаг дотор z[i] = z[i - l] гэж шууд авах. r - i + 1-ээр хязгаарлахгүй бол хайрцгаас гадуурх, шалгаагүй хэсгийг ижил гэж буруу тооцно.
  • while нөхцөлд i + z[i] < n шалгахаа мартвал string-ээс гадуур уншина.
  • Текстээс p хайхдаа p ба s-ийг шууд нийлүүлэх. Дунд нь аль алинд нь байхгүй тэмдэгт (#) тавихгүй бол z утга p-ийн уртаас хэтэрч болно.
  • z[0]-ийг n гэж тооцох эсэх нь бодлогоос хамаарна. Энэ код 0 гэж үлдээдэг.

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

  • n = 1: loop ажиллахгүй, хариу 0.
  • Бүх тэмдэгт ижил, "aaaa": z = [0, 3, 2, 1]. Хайрцаг эхний алхмаар л төгсгөл хүрнэ.
  • Бүх тэмдэгт өөр, "abcd": бүх z тэг. Харьцуулалт бүр шууд зогсоно.

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

  1. s = "abab" бол z ямар байх вэ?

    Хариу харах

    0 0 2 0. 2-р байрлалаас эхэлсэн "ab" нь эхлэлтэй ижил.

  2. s = "aaaa" бол z[1] хэд вэ?

    Хариу харах

    3. "aaa" нь s-ийн эхний гурван тэмдэгттэй ижил, дараа нь string дуусна.

  3. Яагаад хугацаа O(n) вэ?

    Хариу харах

    Амжилттай харьцуулалт бүр r-ыг баруун тийш түлхдэг. r нь n-ээс хэтрэхгүй.

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

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

  1. 1.s = "ababa" string-ийн z утгуудыг гараар ол.

    Hint харах

    2-р байрлалаас эхэлсэн хэсэг "aba". Эхлэлтэй хэдэн тэмдэгтээр ижил вэ?

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

    0 0 3 0 1. z[2] = 3 ("aba"), z[4] = 1 ("a").

  2. 2.s текстээс p хэдэн удаа гарч байгааг Z-function ашиглан тоол. Жишээ: p = "ab", s = "abcab".

    Hint харах

    p + "#" + s string үүсгээд z-ийг нь бод.

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

    "ab#abcab" string-ийн z нь 0 0 0 2 0 0 2 0. z = 2 буюу p-ийн урттай тэнцүү 2 байрлал бий. Хариу 2.

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

    Hint харах

    i + z[i] == n бөгөөд n нь i-д хуваагдах хамгийн бага i-г хай.

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

    "abcabcabc" string-ийн z нь 0 0 0 6 0 0 3 0 0. i = 3 үед 3 + 6 = 9 = n, 9 нь 3-т хуваагдана. Хариу 3. Ийм i байхгүй бол хариу n.

Жишээ

Оролт

abacaba

Гаралт

0 0 1 0 3 0 1