The following assignment is written in the format of a programming contest problem. As is the case with contest problems, input and output specifications are very precise -- you must meet these specifications exactly or you will not receive full credit. Recall that pseudocode for determining the minimal edit distance between two words was provided in the lectures. You will need to augment that approach with caching in order to handle long words.
Your office has just hired a new secretary, whose typing skills leave something to be desired. In fact, it is often difficult to even match the words that appear in the document with the original, intended words. To help decipher these typographic nightmares, you are to write a program that compares two words and determines how close they are to each other.
A word can be transformed using one of three operations
If we associate a cost with each of these operations, then your task is to find the minimal cost by which one word can be transformed into another. For example, consider transforming "abcd" into "acxy". If all three operations have the same cost of 1, then the minimal cost is 3 (delete 'b', substitute 'x' for 'd', and insert 'y'). If substitutions have cost 3 and insertions/deletions have cost 1, then the minimal cost is 4 (delete 'b', delete 'd', insert 'x', and insert 'y').
Input should be read from standard input (
The first line of input will contain three positive integers, representing the
costs of substitutions, insertions, and deletions, respectively. These numbers
will be separated by whitespace, and are guaranteed to be less than or equal to 100.
Following the initial line will be a sequence of lines, each containing two words,
separated by whitespace. The words themselves will consist of no more than 30
characters, and will not contain spaces. Input is terminated by the words "THE END".
Output should be written to standard output (
For each pair of words, you should output the minimal cost of transforming
the first word into the second. Each number should appear on a line by itself.