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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M 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