String Computer

Interview

Time limit1sMemory limit128 MB

Summary

Compute the minimum number of single-character insert, delete, or change operations needed to turn one string into another.

Level: Medium5 of 10
Topics: Dynamic programming, String, Implementation, Brute force
Solved: No attempts yet

Problem

A string-processing computer called the X9091 transforms an input string into a target string. Its instruction set has only three transformation instructions, and each one changes the string currently held in memory:

Delete the character at a given position.
Insert a character at a given position.
Change the character at a given position to a different character.

Each instruction is written as ZXdd, where Z is the operation code (D, I, or C), X is a character, and dd is a two-digit position. A program ends with the halt instruction E. Each instruction acts on the string exactly as it is at the moment the instruction runs.

For example, the string abcde can be transformed into bcgfe by the following program (positions are counted from 1):

     abcde
Da01 bcde    delete the 'a' at position 1
Cg03 bcge    change position 3 to 'g'
If04 bcgfe   insert 'f' at position 4
E    bcgfe   halt

This program uses three transformation instructions (the halt E is not counted), and no shorter program exists for this pair of strings.

Given the input string and the target string, find the minimum number of transformation instructions (delete, insert, or change) needed to turn the input string into the target string.

Input

The input consists of several lines. Each line contains two strings separated by exactly one space: the input string followed by the target string. Each string has at most 20 lowercase letters. The input ends with a line containing a single #.

Output

For each input line, output a single line containing the minimum number of transformation instructions (delete, insert, or change) required to transform the input string into the target string.

Examples3

Example 1
Input
```
abcde bcgfe
#
```
Expected output
```
3
```
Example 2
Input
```
hello hello
#
```
Expected output
```
0
```
Example 3
Input
```
abc abc
abc abd
abc xbc
#
```
Expected output
```
0
1
1
```