ПОДНИЗ

면접 대비

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

요약

두 문자열 a와 b가 주어질 때, a의 순열의 부분문자열이면서 b의 순열의 부분문자열인 가장 긴 문자열을 찾고, 길이가 같으면 사전순으로 가장 작은 것을 출력한다.

문제

소문자 라틴 문자로 이루어진 두 문자열 $a$ 와 $b$ 가 주어진다. $a$ 의 순열의 부분문자열이면서 동시에 $b$ 의 순열의 부분문자열인 문자열 중 가장 긴 것을 찾는 프로그램 substring을 작성하라.

"문자열의 순열"이란 같은 길이를 가지며 원래 문자열의 문자들을 어떤 순서로든 포함하는 문자열을 말한다.

"문자열의 부분문자열"이란 주어진 문자열의 연속한 문자를 0개보다 많이 이어 붙여 만든 문자열을 말한다.

표준 입력에서 두 문자열이 각각 한 줄에 하나씩 주어진다. 각 문자열의 최대 길이는 1000자이다.

표준 출력의 한 줄에 찾은 문자열을 출력한다. 조건을 만족하는 가장 긴 문자열이 여러 개라면 사전 순으로 가장 작은 것을 출력한다.

주어진 문자열은 $a$ 의 순열 uamntu의 부분문자열이면서 $b$ 의 순열 ornamntuet의 부분문자열이다.