57417erlp2GPq9cYqEX's blog

By 57417erlp2GPq9cYqEX, history, 3 years ago, In English

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.

  1. Given two strings S and T can you decide in quadratic time if you can get T by applying this operation once to S?

  2. 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).