두 부분 수열을 담는 최단 문자열

면접 대비

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

요약

주어진 두 문자열을 모두 부분수열로 포함하는 가장 짧은 문자열의 길이를 구합니다.

문제

두 문자열 A와 B가 주어진다.

문자열 S에서 문자를 0개 이상 지우고 남은 문자를 원래 순서대로 이어 붙여 X를 만들 수 있으면, X는 S의 부분 수열이다.

A와 B를 모두 부분 수열로 가지는 문자열 S 가운데 길이가 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

예를 들어 A = "abcbdab", B = "bdcaba"이면 S = "abdcabdab"가 두 조건을 모두 만족하고, 길이가 9보다 짧은 S는 없다.

첫째 줄에 문자열 A가, 둘째 줄에 문자열 B가 주어진다. 두 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 1 이상 1,000 이하이다.

첫째 줄에 A와 B를 모두 부분 수열로 가지는 가장 짧은 문자열의 길이를 출력한다.