시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 158 31 22 44.898%

문제

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

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

입력

첫째 줄에 문자열 O, 둘째 줄에 문자열 N이 주어진다. 문자열의 길이는 최대 1,000이다.

출력

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

예제 입력

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

예제 출력

2

예제 입력 2

aaaaa
ababababa

예제 출력 2

4

예제 입력 3

no way
No way!

예제 출력 3

-1

예제 입력 4

abcefijklmnopuvwxz
abcdefghijklmnopqrstuvwxyz

예제 출력 4

4

힌트

출처