SP7099 ADVEDIST - Advanced Edit Distance

The edit distance of two strings S and T is the minimum number of edit operations that need to be done to transform S into T . The valid edit operations are: • Insert a single character at any position. • Modify an existing character. • Remove an existing character. For example, the edit distance of “pantera” and “aorta” is 5, because the following chain of edits is valid (and there is no shorter chain): “pantera” >>> “antera” >>> “aotera” >>> “aoera” >>> “aora” >>> “aorta”. We define the advanced edit distance in a similar way, but adding the swap of two adjacent characters as an extra valid operation. With this setting, the advanced edit distance of “pantera” and “aorta” is 4: “pantera” >>> “antera” >>> “antra” >>> “aotra” >>> “aorta”. You need to write a program that calculates the advanced edit distance of two given words.

The input contains several test cases. Each test case is described in a single line that contains two non-empty words, each of them of at most 1000 lowercase letters, separated by a single space. The last line of the input contains two asterisks separated by a single space and should not be processed as a test case.

For each test case output a single line with an integer representing the advanced edit distance of the two input words.