Consider the following operation on strings: pick a subsequence, remove it and then append all the characters at the end in the same order. This operation preserves the length of the string.
Given two strings S and T can you decide in quadratic time if you can get T by applying this operation once to S?
Given two strings S and T can you decide in polynomial time if you can get T by applying this operation to S and then applying it once more to the result?
There is a algorithm in cubic time for the first one (for each suffix of T that is also a subsequence of S check if S is an interleaving of that suffix and the corresponding prefix).
Note that there are S and T such that you can get T from S in two operations but not one (e.g. S=abc and T=cba).
Comments (0)
