1
$\begingroup$

Is there a good algorithm for calculating the longest common subsequence where we consider two sequences identical if they can be transformed to one another with at most 1 swapping of subsequences (i.e. taking two non-overlapping subsequences of the same length and substituting them for each other)? For example ABCDEFGHIJ would be considered identical to EFGHABCDIJ but not to ABCDEHFGIJ. Or is there such an algorithm for subsequences of length one?

$\endgroup$
  • $\begingroup$ Have you tried extending the dynamic programming algorithm for LCS? $\endgroup$ – Yuval Filmus May 1 '18 at 14:21
1
$\begingroup$

Swapping two non-overlapping subsequences is same as swapping two non-overlapping substrings of one of the input strings.

A simple algorithm would be to guess the start and end points of the substrings that we want to swap, let them be (s1,t1) and (s2,t2), and run LCS using this swapped string. There are O(m^2*n^2) such guesses and each one takes O(m*n).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.