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.

Input

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.

Output

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

Example

Input:
pantera aorta
zero zero
* *

Output:
4
0

Added by:Pablo Ariel Heiber
Date:2010-08-13
Time limit:22.25s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2007

hide comments
2013-07-05 14:14:27 skrillex
my solution seems to be working well.... but gives me WA... plz provide me some tricky test cases
2010-10-09 18:14:41 Pablo Ariel Heiber
Its irrelevant, note that the allowed transformations are closed by inversion.
2010-09-20 07:10:47 Omar Abd-Elraheem
editing is allowed on both strings or only on the first string ?!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.