Problem Description
I think all of you must be skilled in the classic problem Levenshtein Distance , which is more commonly known as Edit Distance. For more historic knowledge and basic concepts, see http://en.wikipedia.org/wiki/Levenshtein_distance .
This time, we are involved in a more complicated one: given two strings SOURCE and DESTINATION , we have 4 operations
Delete: remove the ith character.
Insert: in pos i(the ith character in the first string),you can insert a character, any one as you like.
Change: in pos i,you can change that original character to any other character(of course you won't change it to itself).
Suffix change: which means you can change all characters to an identical character, from the ith pos to the end. For instance: abcdefg, you can make this operation in character b,maybe you can use d and the result is adddddd, or if you use e the result is aeeeeee or if you use this operation in character c with character f,the result is abfffff.
With the help of Suffix change, sometimes the edit distance can be greatly shortened. See the following example
abcdefg
ccccccg
You can first replace every character from the beginning to the end with c,and the first string will be ccccccc,then change the last character c to g. In such way,we can see the edit distance is 2.
Input
Input consists of several test cases, each case contains two line,the first line will show you the SOURCE string, the second line provide the DESTINATION string. You should write a program to caculate the minimum number of operations(delete, insert, changes, suffix change as I mentioned before) of transforming the SOURCE to DESTINATION. You can assume none of string in any case will be longer than "500". Input ends with a line consists of a '#'.
PAY ATTENTION:Both strings consist of either lower or upper letters,in other word in each position there is 52 possibilities.There will be at most 15 test cases.
Output
One line for each case,the edit distance. Output nothing for the "#".
Sample Input
abcdefg
aaaaaaa
#
Sample Output
1
