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 nonempty 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
hide comments
Somesh Maurya™:
20131027 06:34:13
it is simple Damerau–Levenshtein distance algorithm..but then y it's not getting accepted :C 

skrillex:
20130705 14:14:27
my solution seems to be working well.... but gives me WA... plz provide me some tricky test cases 

Pablo Ariel Heiber:
20101009 18:14:41
Its irrelevant, note that the allowed transformations are closed by inversion. 

Omar AbdElraheem:
20100920 07:10:47
editing is allowed on both strings or only on the first string ?! 
Added by:  Pablo Ariel Heiber 
Date:  20100813 
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 