The edit distance between two words (two sequences of alphanumeric characters) is defined as the minimum number of characters that need to be replaced, added, and/or deleted from the first word to transform it into the second word.
Your task in this problem is to find the edit distance between a given pair of words.
Consider the words “CAT” and “BAT”. The two words only differ in their first character. We only need to replace the “C” in “CAT” with a “B” to arrive at “BAT”. Therefore the edit distance is 1.
The words “FLY” and “FLYING” are identical in their first three characters, but the second word has three additional characters. Adding “ING” to the first word produces the second word. The edit distance in this case is 3.
Consider “GRAVE” and “GROOVY”. We can perform the following substitutions in the first word: (1) “A” ➝ “O”, (2) “E” ➝ “Y”, then (3) insert the character “O” in position 4 (after the first “O”). Thus, the edit distance in this case is 3.
The input will start with an integer N (N > 0) on a line by itself. This is followed by N lines, each of which contains a pair of words. Each word will be no longer than 255 characters, and will contain only non-space alphanumeric characters. The case of alphabetic characters is to be ignored.
For each pair of words, output the pair's sequence number (starting from 1 for the
first pair) followed by “
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|