S와 길이가 같은 두 부분수열, 하나는 S에서 하나는 T에서 뽑아 번갈아 놓아 S를 만들 수 있는지 판정한다.
보통6동적 계획법문자열면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB회사 S의 대표는 회사 T와의 M&A를 준비하고 있다. M&A는 "Mergers and Acquisitions"의 약자다. 대표는 두 회사 이름을 섞어 새 이름을 만든다는 명분을 내세우지만, 실제로 원하는 것은 M&A 뒤에도 원래 이름 S를 그대로 남기는 것이다.
대표가 말하는 합병 후 이름은 다음과 같이 만든다.
s를 S의 부분 수열, t를 T의 부분 수열이라고 하자. 합병 후 이름은 s와 t의 문자를 번갈아 늘어놓아 만든 길이 ∣S∣의 문자열이다. 즉 s0t0s1t1⋯ 또는 t0s0t1s1⋯ 꼴이고, sk는 문자열 s의 k번째(0-based) 문자다. 결과 문자열의 0번, 2번, 4번, ... 자리는 한쪽 부분 수열이 순서대로 채우고 1번, 3번, 5번, ... 자리는 다른 쪽 부분 수열이 순서대로 채운다. ∣S∣가 홀수면 두 부분 수열의 길이가 1만큼 차이 난다.
부분 수열은 원래 문자열에서 문자를 0개 이상 지워서 얻는 문자열이다. 예를 들어 "abe", "abcde", ""(빈 문자열)은 모두 "abcde"의 부분 수열이다.
인수하는 쪽 회사의 프로그래머인 당신은 두 회사 이름을 섞어 원래 이름 S를 만들 수 있는지 판정하는 프로그램을 작성해야 한다.
입력은 테스트 케이스 하나로 이루어지고 두 줄이다.
첫째 줄에 당신이 속한 회사의 이름 S가 주어진다. 둘째 줄에 인수 대상 회사의 이름 T가 주어진다. S와 T는 비어 있지 않고 길이가 서로 같으며, 그 길이는 1,000자를 넘지 않는다. 두 이름은 알파벳 소문자로만 이루어진다.
두 이름을 섞어 원래 회사 이름 S를 만들 수 있으면 첫 줄에 Yes를 출력한다. 만들 수 없으면 No를 출력한다.