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

    solution

    Đề bài: [C] Chuỗi con đối xứng dài nhất — Manacher

    Cho chuỗi sss chỉ gồm chữ thường. Hãy tìm chuỗi con liên tiếp đối xứng (palindrome) dài nhất. In ra độ dài và một chuỗi cụ thể.

    Thuật toán Manacher chạy trong O(n)O(n)O(n): chèn dấu # giữa các ký tự (kèm hai biên ^, $) để xử lý palindrome chẵn/lẻ đồng nhất, sau đó duy trì tâm ccc và biên phải rrr để tận dụng kết quả đối xứng.

    Ví dụ s=s = s= "babad" → một đáp án hợp lệ: độ dài 333, chuỗi bab hoặc aba.

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

      Một dòng chứa chuỗi sss.

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

      1≤∣s∣≤1051 \le |s| \le 10^51≤∣s∣≤105. Chuỗi chỉ gồm chữ cái thường.

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

      Dòng 1: độ dài palindrome dài nhất. Dòng 2: một chuỗi palindrome cụ thể có độ dài đó.

    Ví dụ:

    Đầu vào:

    babad

    Đầu ra:

    3
bab

    Giải thích:

    Có hai palindrome dài 3: bab và aba; in bất kỳ chuỗi nào hợp lệ.

    Đang tải editor...