가희와 철도역

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

요약
S와 T가 같은 문자열로 주어질 때, S를 부분 문자열로 포함하면서 문자를 지워 T를 만드는 방법이 서로 다른 두 가지 이상인 가장 짧은 V를 구한다.
난이도

보통10점 중 6점

유형
문자열, 조합론, 완전 탐색, 수학
정답자
아직 제출이 없습니다

문제

가희는 역명이 VV인 역에 방문한 후, 문자열 SS와 TT를 적었습니다. 그리고 사토에게 수수께끼를 냈습니다.

힌트를 몇 개 줄 테니, 내가 방문한 역명 VV를 맞춰 봐.

  • 문자열 SS는 내가 방문한 역명의 부분 문자열이야.
  • 역명 VV에서 다음 연산을 원하는 만큼 이용해서 문자열 TT를 만들 수 있는 방법은 22가지 이상이야. 이때, VV로부터 하나라도 다른 위치의 문자를 제거하거나, VV로부터 제거한 문자의 개수가 다르면 다른 경우로 세야 해.
    • VV에서 문자를 하나 이상 제거한다.
  • 역명 VV는 영어 대소문자와 숫자로만 이루어져 있고, 가능한 것 중 가장 길이가 짧은 거야.

사토는 가희가 적은 SS와 TT가 같다는 것을 발견하였습니다. 사토를 도와, 가희가 방문한 역명을 구해 주세요.

입력

첫 번째 줄에 문자열 SS가 주어집니다.

두 번째 줄에 문자열 TT가 주어집니다.

출력

첫 번째 줄에 가희가 방문한 역명을 출력해 주세요. 가능한 답이 여러 가지인 경우, 그중 아무것이나 출력해도 정답으로 인정합니다.

제한

  • 문자열 SS와 TT는 영어 대소문자와 숫자로만 구성되어 있으며, 길이는 11 이상 2020 이하입니다. 또한 S=TS = T 입니다.

예제2

  1. 예제 1

    입력
    IllIt
    IllIt
    
    예상 출력
    IIllIt
    
  2. 예제 2

    입력
    tripAndlove
    tripAndlove
    
    예상 출력
    ttripAndlove