DISH

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

요약
각 테스트 케이스에서 두 문자열을 모두 부분 문자열로 포함하는 가장 짧은 문자열을 구해 출력한다.
난이도

보통10점 중 6점

유형
문자열, 동적 계획법, 최단 경로, 문자열 매칭
정답자
아직 제출이 없습니다

문제

카불의 한 식당은 여러 음식을 조합해 새로운 음식을 만들려고 한다. 이 식당은 메뉴를 보여줄 때 손님이 가장 적은 설명으로 음식을 알 수 있도록 각 음식에 이름을 붙이려 한다.

식당 책임자는 새 이름에 주된 음식 이름들이 모두 부분 문자열로 들어가도록 하는 가장 짧은 문자열을 쓰기로 했다. 예를 들어 "shrimpce"는 "rice"와 "shrimp"를 조합해 만든 음식의 이름이며, 같은 성질을 가진 더 짧은 문자열은 없다. 이런 음식들의 가장 짧은 이름을 계산하는 프로그램을 작성하시오.

입력

첫 줄에는 테스트 케이스의 수 NN이 주어진다. 다음 NN개 줄에는 각각 조합할 음식의 이름을 나타내는 두 문자열이 주어진다. 모든 이름의 길이는 최대 100이고 알파벳 문자로만 이루어져 있다.

출력

각 테스트 케이스마다 만들어진 음식의 가장 짧은 이름을 한 줄에 출력한다. 가장 짧은 이름이 여러 개라면 그중 아무거나 출력해도 된다.

예제1

  1. 예제 1

    입력
    3
spaghetti salad
chicken cheese
ananas banana
    예상 출력
    spaghettilad
chickenese
bananas