Đối Xứng Dài Nhất

Buổi 56 — Suffix Array & LCP
Points
42
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho xâu $S$ chỉ gồm các chữ cái in thường. Hãy tìm xâu con đối xứng (palindrome) dài nhất của $S$.

Sử dụng phương pháp mảng hậu tố: nối $S$ với đảo ngược của $S$ (ngăn cách bởi ký tự đặc biệt), rồi tìm xâu con chung dài nhất giữa mỗi tiền tố của $S$ và hậu tố tương ứng của $S^R$.

Nếu có nhiều đáp án cùng độ dài, in ra xâu đầu tiên xuất hiện.

Dữ liệu vào

Một dòng chứa xâu $S$ ($1 \le |S| \le 10^5$) chỉ gồm các chữ cái in thường.

Dữ liệu ra

Một dòng chứa xâu con đối xứng dài nhất.

Ví dụ
Input Output
banana anana
Giới hạn
  • $1 \le |S| \le 10^5$
  • $S$ chỉ gồm chữ cái in thường.
Draft saved