CSES - Longest Palindrome | Xâu đối xứng dài nhất
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một xâu, nhiệm vụ của bạn là xác định xâu con đổi xứng dài nhất của xâu. Ví dụ, xâu đối xứng dài nhất trong aybabtu là bab.
Input
- Dòng đầu vào duy nhất chứa một chuỗi độ dài \(n\). Mỗi kí tự là một trong những
a-z.
Output
- In xâu đối xứng dài nhất trong xâu. Nếu có một số đáp án, bạn có thể in bất kỳ đáp án nào trong số đó.
Constraints
- \(1 \leq n \leq 10^6\)
Example
Test 1
Input
aybabtu
Output
bab
Bình luận
**Hint**
$Manacher's$ $Algorithm$
-
0
huyhau6a2
5:30 p.m. 18 Tháng 9, 2022
4 bình luận nữaTa có thể áp dụng binary search+hashing để tìm xâu đối xứng dài nhất. Ở đây ta xét từng ký tự thứ \(i\), ta sẽ dùng binary search để tìm số \(x\) lớn nhất thỏa mãn \(a[i-x->i+x]\) là xâu đối xứng. Với cặp ký tự gồm 2 ký tự giống nhau cũng thực hiện tương tự để tìm độ dài với giá trị chẵn
Độ phức tạp lớn nhất là \(O(2n.log(n))\)