아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

M and A

면접 대비

시간 제한5초메모리 제한512 MB

요약
S와 길이가 같은 두 부분수열, 하나는 S에서 하나는 T에서 뽑아 번갈아 놓아 S를 만들 수 있는지 판정한다.
난이도

보통10점 중 6점

유형
동적 계획법, 문자열
정답자
아직 제출이 없습니다

문제

회사 S의 대표는 회사 T와의 M&A를 준비하고 있다. M&A는 "Mergers and Acquisitions"의 약자다. 대표는 두 회사 이름을 섞어 새 이름을 만든다는 명분을 내세우지만, 실제로 원하는 것은 M&A 뒤에도 원래 이름 S를 그대로 남기는 것이다.

대표가 말하는 합병 후 이름은 다음과 같이 만든다.

s를 S의 부분 수열, t를 T의 부분 수열이라고 하자. 합병 후 이름은 s와 t의 문자를 번갈아 늘어놓아 만든 길이 ∣S∣|S|의 문자열이다. 즉 s0t0s1t1⋯s_0 t_0 s_1 t_1 \cdots 또는 t0s0t1s1⋯t_0 s_0 t_1 s_1 \cdots 꼴이고, sks_k는 문자열 s의 kk번째(0-based) 문자다. 결과 문자열의 0번, 2번, 4번, ... 자리는 한쪽 부분 수열이 순서대로 채우고 1번, 3번, 5번, ... 자리는 다른 쪽 부분 수열이 순서대로 채운다. ∣S∣|S|가 홀수면 두 부분 수열의 길이가 1만큼 차이 난다.

부분 수열은 원래 문자열에서 문자를 0개 이상 지워서 얻는 문자열이다. 예를 들어 "abe", "abcde", ""(빈 문자열)은 모두 "abcde"의 부분 수열이다.

인수하는 쪽 회사의 프로그래머인 당신은 두 회사 이름을 섞어 원래 이름 S를 만들 수 있는지 판정하는 프로그램을 작성해야 한다.

입력

입력은 테스트 케이스 하나로 이루어지고 두 줄이다.

첫째 줄에 당신이 속한 회사의 이름 S가 주어진다. 둘째 줄에 인수 대상 회사의 이름 T가 주어진다. S와 T는 비어 있지 않고 길이가 서로 같으며, 그 길이는 1,000자를 넘지 않는다. 두 이름은 알파벳 소문자로만 이루어진다.

출력

두 이름을 섞어 원래 회사 이름 S를 만들 수 있으면 첫 줄에 Yes를 출력한다. 만들 수 없으면 No를 출력한다.

예제3

  1. 예제 1

    입력
    acmicpc
    tsukuba
    
    예상 출력
    No
    
  2. 예제 2

    입력
    hoge
    moen
    
    예상 출력
    Yes
    
  3. 예제 3

    입력
    abcdefg
    xacxegx
    
    예상 출력
    Yes