가장 짧은 비공통 부분 수열
시간 제한2초메모리 제한128 MB
문자열 A와 B가 주어질 때, A의 부분수열이지만 B의 부분수열은 아닌 가장 짧은 문자열의 길이를 구합니다.
문제
문자열 A에서 문자를 하나 이상 골라 원래 순서를 유지한 채 이어 붙이면 A의 부분 수열이 된다. 고른 문자들은 서로 이웃할 필요가 없다.
두 문자열 A와 B가 주어진다. A의 부분 수열이면서 B의 부분 수열은 아닌 문자열 중 길이가 가장 짧은 것의 길이를 구하라.
입력
첫째 줄에 문자열 A, 둘째 줄에 문자열 B가 주어진다. 두 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 1000 이하이다. 입력은 항상 답이 존재하는 경우만 주어진다.
출력
첫째 줄에 A의 부분 수열이면서 B의 부분 수열이 아닌 가장 짧은 문자열의 길이를 출력한다.