String Distance

Time limit2sMemory limit128 MB

Summary
Given strings O and N, find the minimum number of substring-insertion operations to turn O into N, or output -1 if impossible.
Level

Medium6 of 10

Topics
Dynamic programming, String, String matching, Array
Solved
No attempts yet

Problem

The string distance from string O to string N is the minimum number of string insertion operations needed to make O equal to N. In one operation, you may insert any string at any position in O, including the beginning, the end, or between two existing characters.

Given two strings O and N, compute the string distance from O to N.

Input

The first line contains string O, and the second line contains string N. Each string has length at most 1,000. Every character has an ASCII code from 32 through 126, inclusive. The whole line is part of the string, so spaces are significant.

Output

Print the string distance from O to N on the first line. If it is impossible to make O equal to N, print -1.

Examples4

  1. Example 1

    Input
    hello fine
hello, how are you? I'm fine thank you and you?
    Expected output
    2

  2. Example 2

    Input
    aaaaa
ababababa
    Expected output
    4

  3. Example 3

    Input
    no way
No way!
    Expected output
    -1

  4. Example 4

    Input
    abcefijklmnopuvwxz
abcdefghijklmnopqrstuvwxyz
    Expected output
    4