CSC 427: Data Structures and Algorithm Analysis
Fall 2007

HW6: Recursion & Dynamic Programming

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

  1. Substitution: a character can be substituted for another anywhere in the word, e.g., "heblo" --> "hello"
  2. Insertion: a character can be inserted anywhere in the word, e.g., "ace" --> "face"
  3. Deletion: a character can be deleted anywhere in the word, e.g., "foool" --> "fool"

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 (System.out). 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.


1 1 1 abc abc abc abd abcd acxy THE END


0 1 3