Đối Xứng Dài Nhất
Points
42
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Đề 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.
Community Discussion