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

    solution

    Đề bài: [C] Tìm chuỗi con chung dài nhất (LCS) và truy vết

    Hai phòng ban gửi hai chuỗi văn bản sss và ttt. Hãy tìm chuỗi con chung dài nhất (không nhất thiết liên tiếp) và truy vết một chuỗi LCS cụ thể.

    DP: dp[i][j]dp[i][j]dp[i][j] là LCS của s[0..i)s[0..i)s[0..i) và t[0..j)t[0..j)t[0..j). Nếu si−1=tj−1s_{i-1} = t_{j-1}si−1​=tj−1​ thì dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i-1][j-1] + 1dp[i][j]=dp[i−1][j−1]+1, ngược lại dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = \max(dp[i-1][j], dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1]).

    Truy vết từ (n,m)(n, m)(n,m) về (0,0)(0, 0)(0,0) để dựng chuỗi.

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

      Một dòng chứa hai chuỗi sss và ttt cách nhau bởi dấu cách.

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

      1≤∣s∣,∣t∣≤10001 \le |s|, |t| \le 10001≤∣s∣,∣t∣≤1000. Chuỗi gồm chữ cái Latin.

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

      Dòng 1: độ dài LCS. Dòng 2: một chuỗi LCS bất kỳ (nếu độ dài 0 thì in dòng trống).

    Ví dụ:

    Đầu vào:

    ABCBDAB BDCABA

    Đầu ra:

    4
BCBA

    Giải thích:

    LCS có độ dài 4, một đáp án hợp lệ: BCBA hoặc BDAB.

    Đang tải editor...