Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Xâu con đối xứng dài nhất

    Cho xâu SSS. Một xâu con đối xứng (palindrome) là xâu con liên tiếp đọc xuôi và đọc ngược giống nhau.

    Hãy tìm độ dài của xâu con đối xứng dài nhất trong SSS. Sử dụng thuật toán Manacher chạy trong O(∣S∣)O(|S|)O(∣S∣).

    Ví dụ: S=S = S= babad có các xâu con đối xứng bab và aba (độ dài 333), nên đáp án là 333.

    • Định dạng đầu vào:

      Một dòng chứa xâu SSS gồm các chữ cái la-tinh thường.

    • Ràng buộc đầu vào:

      1≤∣S∣≤1061 \le |S| \le 10^61≤∣S∣≤106.

    • Định dạng đầu ra:

      In ra một số nguyên là độ dài xâu con đối xứng dài nhất.

    Ví dụ:

    Đầu vào:

    babad

    Đầu ra:

    3

    Giải thích:

    Các xâu con đối xứng dài nhất là bab và aba, cùng có độ dài 3. Không có xâu đối xứng nào dài hơn nên đáp án là 3.

    Đang tải editor...