사전 순 최대 공통 부분 수열
시간 제한1초메모리 제한1024 MB
길이 100 이하인 두 양의 정수 수열의 공통 부분 수열 가운데 사전 순으로 가장 뒤인 것을 찾는다.
문제
어떤 수열이 다른 수열의 부분 수열이라는 것은 다음을 의미합니다.
- 해당 수열의 원소들이 다른 수열 내에서 순서대로 등장합니다.
- 예를 들어, 는 의 부분 수열이지만, 의 부분 수열은 아닙니다.
또한, 어떤 수열이 다른 수열보다 사전 순으로 나중이라는 것은 다음을 의미합니다.
- 두 수열 중 첫 번째 수가 큰 쪽은 사전 순으로 나중입니다.
- 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 빼고 두 수열을 다시 비교했을 때 사전 순으로 나중인 쪽이 사전 순으로 나중입니다.
- 길이가 인 수열과 다른 수열을 비교하면, 다른 수열이 사전 순으로 나중입니다.
양의 정수로 이루어진 길이가 인 수열 이 주어집니다. 마찬가지로 양의 정수로 이루어진 길이가 인 수열 이 주어집니다.
수열 와 수열 가 공통으로 갖는 부분 수열들 중 사전 순으로 가장 나중인 것을 구하세요.
입력
첫 줄에 수열 의 길이 이 주어집니다.
둘째 줄에 개의 양의 정수 이 주어집니다.
셋째 줄에 수열 의 길이 이 주어집니다.
넷째 줄에 개의 양의 정수 이 주어집니다.
출력
와 의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 를 출력하세요.
이라면, 다음 줄에 개의 수를 공백으로 구분해 출력하세요. 번째 수는 와 의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 번째 수입니다.