Dãy con chung dài nhất (Phiên bản 2)

Xem PDF

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Cho dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1,A_2,\cdots,A_N\) và dãy \(B\) gồm \(M\) phần tử gồm các số nguyên dương \(B_1,B_2,\cdots,B_M\). Dãy \(C\) được gọi là dãy con chung độ dài \(K\) của \(A,B\) nếu tồn tại hai dãy chỉ số như sau:

  • \(1 \leq i_1 < i_2 < \cdots < i_K \leq N\).
  • \(1 \leq j_1 < j_2 < \cdots < j_K \leq M\).
    Sao cho \(C_p = A_{i_p} = B_{j_p}\).

Yêu cầu: Tìm dãy \(C\) là dãy con chung của \(A,B\) sao cho độ dài \(K\) lớn nhất có thể.

Input

  • Dòng thứ nhất chứa hai số nguyên dương \(N,M\).
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1,A_2,\cdots,A_N (A_i \leq 10^6)\).
  • Dòng thứ ba gồm \(M\) số nguyên dương \(B_1,B_2,\cdots,B_M (B_i \leq 10^6)\).

Output

  • Dòng thứ nhất in ra số \(K\) là độ dài dãy con chung \(C\) dài nhất tìm được.
  • Dòng thứ hai in ra \(K\) số nguyên dương \(C_1,C_2,\cdots,C_K\). Nếu có nhiều dãy \(C\) thoả mãn, in ra một dãy bất kì.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^3,M \leq 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^3,M \leq 10^6\).

Nếu in ra đúng số \(K\) thì sẽ được 50% số điểm của test. Nếu in ra thêm được dãy \(C_1,C_2,\cdots,C_K\) mà đúng sẽ được thêm 50% số điểm của test

Example

Test 1

Input
9 9 
1 2 7 3 4 8 5 6 9 
1 2 3 4 5 6 7 8 9 
Output
7 
1 2 3 4 5 6 9

Bình luận


  • -2
    minhtuanitk20 7:48 p.m. 28 Tháng 10, 2021

    khó thực sự


    • -7
      minhtuanitk20 7:41 p.m. 28 Tháng 10, 2021

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


      • 0
        bin9638 4:19 p.m. 11 Tháng 8, 2020

        Em mới đọc qhđ đảo nhãn xâu con chung dài nhất nhưng bài này làm sao tính được hàm next vậy anh, vì bài này dãy A tệ nhất có N số khác nhau r @@


        • 0
          lengvan 11:09 a.m. 7 Tháng 8, 2020

          em bị failed initializing là bị gì thế mn?

          2 phản hồi

          • 0
            vinhntndu 9:29 p.m. 6 Tháng 8, 2020

            2 for never die 🙂

            1 phản hồi

            • 0
              dangquan6b 8:14 p.m. 6 Tháng 8, 2020

              Sao bài khó thế 🙁

              1 phản hồi

              • 0
                dangquan6b 4:45 p.m. 6 Tháng 8, 2020

                Nai xừ 🙂