Xâu con đối xứng

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Cho một xâu ký tự \(s\) chỉ gồm các chữ cái latin thường. Hãy tìm một xâu con đối xứng dài nhất gồm các ký tự liên tiếp của xâu \(s\).

Input

Một dòng duy nhất chứa xâu \(s\ (1\leq |s|\leq 1000)\).

Output

Một số nguyên dương duy nhất là độ dài xâu con đối xứng dài nhất tìm được.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

xyzzyz

Output

4

Giải thích ví dụ

Ví dụ

Ví dụ 2

Input

xyzzyz

Output

4

Giải thích ví dụ

Giải thích: Xâu con đối xứng dài nhất là "yzzy" hoặc "zzyz", cả hai đều có độ dài 4.

Thông tin học tập

• Buổi: B21
• Concepts: std::string, center expansion, two indices, O(n^2) optimization
• Giới hạn kiến thức: B01-B21
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 20