가희와 철도역
시간 제한1초메모리 제한512 MB
S와 T가 같은 문자열로 주어질 때, S를 부분 문자열로 포함하면서 문자를 지워 T를 만드는 방법이 서로 다른 두 가지 이상인 가장 짧은 V를 구한다.
문제
가희는 역명이 인 역에 방문한 후, 문자열 와 를 적었습니다. 그리고 사토에게 수수께끼를 냈습니다.
힌트를 몇 개 줄 테니, 내가 방문한 역명 를 맞춰 봐.
- 문자열 는 내가 방문한 역명의 부분 문자열이야.
- 역명 에서 다음 연산을 원하는 만큼 이용해서 문자열 를 만들 수 있는 방법은 가지 이상이야. 이때, 로부터 하나라도 다른 위치의 문자를 제거하거나, 로부터 제거한 문자의 개수가 다르면 다른 경우로 세야 해.
- 에서 문자를 하나 이상 제거한다.
- 역명 는 영어 대소문자와 숫자로만 이루어져 있고, 가능한 것 중 가장 길이가 짧은 거야.
사토는 가희가 적은 와 가 같다는 것을 발견하였습니다. 사토를 도와, 가희가 방문한 역명을 구해 주세요.
입력
첫 번째 줄에 문자열 가 주어집니다.
두 번째 줄에 문자열 가 주어집니다.
출력
첫 번째 줄에 가희가 방문한 역명을 출력해 주세요. 가능한 답이 여러 가지인 경우, 그중 아무것이나 출력해도 정답으로 인정합니다.
제한
- 문자열 와 는 영어 대소문자와 숫자로만 구성되어 있으며, 길이는 이상 이하입니다. 또한 입니다.