Paper Cuts
시간 제한1초메모리 제한512 MB
원본 문자열을 연속한 블록으로 나누어 재배열해 목표 문자열을 만들 때 블록 수를 최소로 줄이고 이 수에서 1을 뺀 값을 답으로 출력합니다.
문제
Tito는 어떤 글자들이 적힌 종이 조각을 가지고 있다. 그는 세로로 몇 번 자른 뒤 남은 종이 조각들을 재배열해서 다른 단어를 만들고 싶어 한다. 예를 들어, 다음과 같은 글자들이 적힌 종이 조각은
abbaaddccee
네 조각으로 자를 수 있고,
abb | aa | ddcc | ee
다른 순서로 이어 붙일 수 있다.
aaabbeeddcc
Tito의 종이 조각과 그가 만들고 싶어 하는 단어가 주어졌을 때, 원하는 단어를 만들기 위해 Tito가 해야 하는 최소 컷 수를 구하여라.
입력
첫 번째 줄에는 Tito의 종이 조각을 나타내는 소문자로 이루어진 문자열이 주어진다.
두 번째 줄에는 Tito가 글자를 재배열해서 만들고 싶어 하는 단어를 나타내는 소문자로 이루어진 문자열이 주어진다.
두 줄은 길이가 1 이상 18 이하로 같고, 두 줄을 이루는 글자들이 정확히 같다는 것이 보장된다. 즉, 종이 조각의 글자들을 재배열해서 Tito가 원하는 단어에 도달하는 것이 항상 가능하다.
출력
Tito가 해야 하는 최소 컷 수를 한 줄에 출력하여라.