Тэмдэгт мөрийн функцууд

2s

512MB

1625

0%

String Algorithms

$1,2,\dots,n$ гэж дугаарлагдсан $n$ тэмдэгт бүхий тэмдэгт мөрийг авч үзье. Дараах функцийн бүх утгыг тооц:

$z(i)$ нь $i$ байрлалд эхлж, тэмдэгт мөрийн префикс байдаг дэд мөрийн хамгийн их урт. Мөн $z(1)=0$ .
$\pi(i)$ нь $i$ байрлалд төгсөж, тэмдэгт мөрийн префикс байдаг ба урт нь $i-1$ -ээс хэтэрдэггүй дэд мөрийн хамгийн их урт.

$z$ функцийг Z-алгоритмд, $\pi$ функцийг KMP алгоритмд ашигладаг.

Цор ганц мөрөнд $n$ урттай тэмдэгт мөр байна. Тэмдэгт бүр a–z-ийн аль нэг нь.

Хоёр мөр хэвлэ: эхэнд $z$ функцийн утгууд, дараа нь $\pi$ функцийн утгууд.

Оролт1

abaabca

Гаралт1

0 0 1 2 0 0 1
0 0 1 1 2 0 1

0.1 / 64 KiB

Редактор уншиж байна...