최단 공통 비부분열
시간 제한5초메모리 제한512 MB
길이가 최대 4000인 두 이진 문자열이 주어질 때, 어느 쪽의 부분수열도 아닌 가장 짧은 이진 문자열을 사전순으로 가장 작게 구한다.
문제
수열 P의 부분열이란 P에서 원소를 몇 개 고르거나 아예 고르지 않고 순서를 유지한 채 얻을 수 있는 수열이다. 예를 들어 “ICPC”는 “MICROPROCESSOR”의 부분열이다.
두 수열의 공통 부분열이란 두 수열 모두의 부분열인 수열이다. 잘 알려진 최장 공통 부분열 문제는 주어진 두 수열의 공통 부분열 가운데 가장 긴 것을 찾는 문제이다.
이 문제에서는 반대로 최단 공통 비부분열 문제를 다룬다. 0과 1로 이루어진 두 수열이 주어지면, 두 수열 어느 쪽의 부분열도 아닌 0과 1로 이루어진 가장 짧은 수열을 찾아야 한다.
입력
입력은 두 줄로 이루어진 단일 테스트 케이스이다. 두 줄 모두 0과 1로만 이루어진 수열이다. 길이는 각각 1 이상 4000 이하이다.
출력
주어진 두 수열의 최단 공통 비부분열을 한 줄에 출력한다. 그러한 수열이 둘 이상이면 사전 순으로 가장 앞서는 것을 출력한다. 여기서 길이가 같은 두 수열 P와 Q에 대해, P1 = Q1, ..., Pk−1 = Qk−1이고 Pk < Qk인 k가 존재하면 P가 Q보다 사전 순으로 앞선다고 한다. 여기서 Si는 수열 S의 i번째 문자이다.