String-ийн бүх палиндромыг өмнө олсон палиндромын толин тусгалыг ашиглан O(n) хугацаанд олдог арга.

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

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

s = "aba" string-д хэдэн палиндром хэсэг байна вэ? "a", "b", "a" гэсэн гурван ганц тэмдэгт, бас бүтэн "aba". Нийт 4, хамгийн урт нь 3 тэмдэгт.

# тавибал t = "#a#b#a#". b тэмдэгтийн байрлал 3 дээр d[3] = 4: "#a#b#a#" бүтнээрээ палиндром.

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

Энгийн арга: төв бүрээс хоёр тийш тэлнэ. "aaaa…a" дээр төв бүрт n хүртэл алхам хийгээд нийт O(n²).

Гол санаа: Z-function-ий хайрцагтай адил. [l, r] нь хамгийн баруун тийш хүрсэн палиндром. i хайрцаг дотор байвал хайрцгийн төвийн нөгөө талд толин тусгал j = l + r - i бий. Палиндромын хоёр тал ижил тул d[j] бэлэн хариу болно. Хайрцгаас гарсан хэсгийг л шинээр шалгана.

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

t
Тэмдэгт бүрийн хооронд болон хоёр захад # тавьсан string. n тэмдэгттэй s-ээс 2n + 1 урттай t гарна.
d[i]
t[i] төвтэй хамгийн урт палиндромын радиус. d[i] = k бол t[i - k + 1..i + k - 1] палиндром.
[l, r]
Одоогоор хамгийн баруун тийш хүрсэн палиндром.
j = l + r - i
Хайрцгийн төвийн нөгөө талд байгаа i-н толин тусгал.
d[i] / 2
Энэ төвтэй, s дотор байгаа палиндромын тоо.
012345678t
#
a
#
b
#
b
#
a
#
d
l = 0r = -1cnt = 0best = 0

s = "abba". Бүх палиндромыг олъё. Тэмдэгт бүрийн хооронд # тавибал тэгш, сондгой урттай палиндром хоёулаа төвтэй болно. d[i] бол i төвтэй хамгийн урт палиндромын радиус. Шар хайрцаг [l, r] бол хамгийн баруун тийш хүрсэн палиндром.

Алхам 1 / 27
Хурд
  • Төв i
  • Палиндром
  • Шинээр шалгасан хос
  • Хайрцаг [l, r]
  • Толин тусгал j
  • # тэмдэг
Слайд 1 / 6

Палиндром

Урдаас ч, араас ч ижил уншигддаг string-ийг палиндром гэнэ: "abba", "aba". Ганц тэмдэгт ч палиндром. s дотор хэдэн палиндром хэсэг байгааг, хамгийн урт нь аль болохыг олъё.

manacher.cpp
#include <bits/stdc++.h>
using namespace std;
string s, t;
int d[200005], l, r = -1, best;
long long cnt;
int main() {
cin >> s;
for (char c : s) t += string("#") + c;
t += '#';
int n = t.size();
for (int i = 0; i < n; i++) {
int k = 1;
if (i <= r) {
k = min(d[l + r - i], r - i + 1);
}
while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) {
k++;
}
cnt += k / 2;
best = max(best, k - 1);
d[i] = k;
if (i + k - 1 > r) {
l = i - k + 1;
r = i + k - 1;
}
}
cout << cnt << ' ' << best << '\n';
return 0;
}

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

String дотор хэдэн палиндром хэсэг байгааг, хамгийн урт палиндромыг олох. Төв бүрээс хоёр тийш тэлэх энгийн арга O(n²), Manacher O(n).

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

1. Тэмдэгт бүрийн хооронд # тавина: "abba" → "#a#b#b#a#". Ингэвэл тэгш, сондгой урттай палиндром хоёулаа нэг төвтэй болно. 2. d[i] бол t[i] төвтэй хамгийн урт палиндромын радиус. [l, r] бол хамгийн баруун тийш хүрсэн палиндром. 3. i хайрцаг дотор бол толин тусгал j = l + r − i байрлалын d[j]-г ашиглана: k = min(d[j], r − i + 1). 4. Хоёр талын тэмдэгт ижил байх хүртэл k-г нэмнэ. d[i] / 2 нь энэ төвтэй палиндромын тоо. Оролт: нэг мөрөнд string. Гаралт: палиндром хэсгийн тоо ба хамгийн урт палиндромын урт.

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

Хайрцаг палиндром тул j-н эргэн тойрон i-н эргэн тойронтой толин тусгал шиг ижил. Тиймээс хайрцаг дотор d[j]-д итгэж болно. Хайрцгаас цааш юу байгааг мэдэхгүй тул r - i + 1-ээр хязгаарлаад, үлдсэнийг while loop шалгана.

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

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

  • # тавихгүйгээр зөвхөн сондгой урттай палиндромыг тоолох. "abba" шиг тэгш урттайг алдана.
  • Толин тусгалын индексийг l + r - i биш r - i гэж бичих.
  • Палиндромын тоог int-д хадгалах. "aaa…a" дээр тоо нь n(n + 1) / 2, n = 100 000 бол 5 тэрбум гарч int хэтэрнэ. cnt нь long long.
  • Хариуны уртыг d[i] гэж буруу авах. s дотор урт нь d[i] - 1.

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

  • n = 1: нэг палиндром, хамгийн урт нь 1.
  • Бүх тэмдэгт өөр, "abc": зөвхөн ганц тэмдэгтүүд, хариу 3 1.
  • Бүх тэмдэгт ижил, "aaa": хэсэг бүр палиндром, хариу 6 3.

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

  1. "aaa" string-д хэдэн палиндром хэсэг бий вэ?

    Хариу харах

    6: "a" гурав, "aa" хоёр, "aaa" нэг.

  2. s нь 5 тэмдэгттэй бол t хэдэн тэмдэгттэй вэ?

    Хариу харах

    11. 2 · 5 + 1.

  3. d[i] = 5 бол s дотор хамгийн урт палиндром хэдэн тэмдэгт вэ?

    Хариу харах

    4. d[i] - 1.

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

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

  1. 1."aba" string-ийн t ба d-г гараар бич.

    Hint харах

    t = "#a#b#a#". # төв дээр d нь 1 эсвэл түүнээс их.

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

    d = [1, 2, 1, 4, 1, 2, 1]. d / 2-ын нийлбэр 0 + 1 + 0 + 2 + 0 + 1 + 0 = 4.

  2. 2.Кодыг хамгийн урт палиндромын эхлэх байрлалыг хэвлэдэг болго.

    Hint харах

    best шинэчлэгдэх үед t дотор эхлэх байрлал нь i - k + 1. s дотор хэд болох вэ?

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

    best шинэчлэгдэх бүрт start = (i - k + 1) / 2 гэж хадгална. Учир нь t дахь # тэмдгүүд индексийг хоёр дахин томруулсан. "racecar" дээр start = 0, урт 7.

  3. 3.String-ийн бүх палиндром хэсгийг Manacher-гүйгээр, гэхдээ O(n²) хугацаанд тоол. n = 2000 хүртэл хангалттай юу?

    Hint харах

    2n − 1 төв бүрээс хоёр тийш тэл.

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

    Төв бүрээс тэлэхэд нийт n² орчим алхам. n = 2000 бол 4 сая, хангалттай. n = 100 000 бол 10 тэрбум тул Manacher хэрэгтэй.

Жишээ

Оролт

abba

Гаралт

6 4