Edit distance with move operations Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the structure) and doing local edits. Is it really so hard to get it right?



Definitions: I would like to find the minimum edit distance, where the permitted operations are:


"cheap" operations: add/change/delete a single character (the usual Levenshtein operations),
"expensive": operations: move a substring to a new location ($abcd \mapsto acbd$ for any strings $a$, $b$, $c$, $d$).


Given two strings $x$ and $y$ and integers $k$ and $K$, I would like to solve the following problem:


can you transform $x$ into $y$ using at most $k$ cheap operations and at most $K$ expensive operations?




Questions:


Does this problem have a name? (It sounds like a very standard question in the context of sequence alignment.)
Is it hard?
If it is hard, is it fixed-parameter tractable with $K$ as the parameter?
Are there efficient approximation algorithms? (E.g., find a solution with at most $2k$ cheap and $2K$ expensive operations if a solution with $k$ cheap and $K$ expensive operations exist.)


I tried to have a look at the string metrics listed in Wikipedia, but none of them looked right.
As commented by Serge Gaspers, for $k=0$ the problem is Sorting by Transpositions, and was introduced by Bafna and Pevzner in 1995. Its NP-hardness has been proved only in 2010; see Laurent Bulteau, Guillaume Fertin, and Irena Rusu, "Sorting by Transpositions is Difficult".