We are given two strings, called the source and the target, which both have the same number of characters n. The goal is to transform the target string into the source string using the smallest number of allowed operations. There are two types of allowed operations, a flip and a substitution.

• A substitution replaces a character in a certain position by another character. For example eetie is transformed to eerie via a substitution of the third character.
• A flip reverses a contiguous substring of the string. In particular, flip(i,j) reverses the substring starting at the i-th character and ending at the j-th character. For example, eteie is transformed to eetie via flip(2,3).

We should assume that the portions where any two flips are applied don't overlap. That is, if we perform flip(i,j) and flip(k,l), then the sets {i,i+1,...,j} and {k,k+1,...,l} are disjoint.

Consider the source string timeflieslikeanarrow and the target string tfemiliilzejeworrbna. The following sequence transforms the target into the source:

1. tfemiliilzejeworrbna (the target)
2. tfemiliilzejeanbrrow (a flip)
3. tfemiliezlijeanbrrow (a flip)
4. timefliezlijeanbrrow (a flip)
5. timefliezlijeanarrow (a substitution)
6. timefliezlikeanarrow (a substitution)
7. timeflieslikeanarrow (a substitution)

The number of operations used, which is the quantity we seek to minimize, was 6. Note that we never need more operations than the length of the given strings.

Write a time-efficient program that takes as input a file containing the two input strings and prints out a minimum length sequence of transformations from the target to the source. You can assume that the file is formatted like this example. Each string will be a sequence of lower-case English characters. Note that for the grading we plan to measure time-efficiency by actual running time on strings of length up to a few hundreds. With this mind, we strongly recommend in this case that you design a polynomial time algorithm to implement. As background reading for designing your algorithm, it may help to study the dynamic programming approach to compute the edit distance between two strings. Please see Section 5.5 of Jeff Erickson's Notes.

Your submission for this homework should consist of two files: (a) your source code (b) a document with some text describing your algorithm and instructions on how to compile and/or run your program with a given input file. Submit these into a dropbox folder on ICON named Homework7

[Update Nov 21] Here is one more example to consider, and here is another related one.