가장 짧은 비공통 부분 수열

문자열 A에서 문자를 하나 이상 골라 원래 순서를 유지한 채 이어 붙이면 A의 부분 수열이 된다. 고른 문자들은 서로 이웃할 필요가 없다.

두 문자열 A와 B가 주어진다. A의 부분 수열이면서 B의 부분 수열은 아닌 문자열 중 길이가 가장 짧은 것의 길이를 구하라.

첫째 줄에 문자열 A, 둘째 줄에 문자열 B가 주어진다. 두 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 1000 이하이다. 입력은 항상 답이 존재하는 경우만 주어진다.

첫째 줄에 A의 부분 수열이면서 B의 부분 수열이 아닌 가장 짧은 문자열의 길이를 출력한다.