시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB67414611131.534%

문제

문자열 O에서 문자열 N까지 문자열 거리는 O를 N과 같게 만들기 위해 필요한 문자열 삽입의 최솟값이다. 문자열 삽입은 O의 어느 위치에서건 가능하다. 예를 들어, O가 “gosrl"일 때, ”sip gi"을 r이전에 삽입한다면 "gossip girl“이 된다.

문자열 O와 문자열 N이 주어질 때, 두 문자열의 거리를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 O, 둘째 줄에 문자열 N이 주어진다. 문자열의 길이는 최대 1,000이다. 문자열은 아스키 코드의 값이 32보다 크거나 같고, 126보다 작거나 같은 문자로만 이루어져 있다.

출력

첫째 줄에 문자열 O와 문자열 N의 문자열 거리를 출력한다. 만약 O를 N으로 만들 수 없다면 -1을 출력한다.

예제 입력 1

hello fine
hello, how are you? I'm fine thank you and you?

예제 출력 1

2

예제 입력 2

aaaaa
ababababa

예제 출력 2

4

예제 입력 3

no way
No way!

예제 출력 3

-1

예제 입력 4

abcefijklmnopuvwxz
abcdefghijklmnopqrstuvwxyz

예제 출력 4

4

출처