Mảng Z Cơ Bản

Buổi 54 — KMP & Z-function
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho xâu $S$ có độ dài $n$ (đánh chỉ số từ $0$). Mảng $Z$ của $S$ được định nghĩa như sau:

  • $Z[0] = 0$.
  • Với mọi $1 \le i < n$, $Z[i]$ là độ dài tiền tố chung dài nhất (LCP) giữa $S$ và hậu tố $S[i..n-1]$.

Hãy tính và in ra toàn bộ mảng $Z$ của xâu $S$.

Dữ liệu vào
  • Một dòng duy nhất chứa xâu $S$ ($1 \le |S| \le 10^6$).
Dữ liệu ra
  • Gồm $n$ số nguyên $Z[0], Z[1], \dots, Z[n-1]$ cách nhau bởi dấu cách.
Ví dụ
Input Output
aaaaa 0 4 3 2 1
abacaba 0 0 1 0 3 0 1
Giới hạn
  • $1 \le |S| \le 10^6$, chỉ gồm các chữ cái 'a'–'z'.
Draft saved