Mật Khẩu Bí Ẩn

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

Cho xâu $S$. Hãy tìm xâu $T$ khác rỗng dài nhất thỏa mãn đồng thời 3 điều kiện:

  1. $T$ là tiền tố thực sự của $S$ ($|T| < |S|$).
  2. $T$ là hậu tố thực sự của $S$.
  3. $T$ xuất hiện ít nhất một lần ở bên trong $S$ (tức là ở vị trí bắt đầu khác $0$ và vị trí kết thúc khác $|S|-1$).

Nếu không tồn tại xâu $T$ nào như vậy, hãy in ra NONE.

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
  • Xâu $T$ dài nhất thỏa mãn, hoặc NONE nếu không tồn tại.
Ví dụ
Input Output
fixprefixsuffix fix
abcdabc NONE
Giới hạn
  • $1 \le |S| \le 10^6$, chỉ gồm các chữ cái 'a'–'z'.
Draft saved