Transform a string into another one by removing a subsequence and appending it at the end

Правка en1, от 57417erlp2GPq9cYqEX, 2021-06-04 17:30:24

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

Теги strings, dynamic programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский 57417erlp2GPq9cYqEX 2021-06-04 17:30:24 862 Initial revision (published)