Consider the following problem. I have a pattern $P$ of length $100$ and a text $T$ of length $n$. I want to find the minimum number of operations to transform $P$ into $T$. The operations are:

  • Insert a single character into $P$
  • Delete a single character from $P$
  • Substitute a single character in $P$ for another one
  • Move an entire substring of $P$ to another location in $P$

What is the time complexity of this problem?

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Have you looked at the dynamic programming algorithms for Levenshtein edit distance to see if it can be extended/generalized to this problem? We expect people to make a serious effort on their own before asking, and to show us what research they've done and what they've tried. $\endgroup$
    – D.W.
    Commented Jun 18, 2014 at 17:54
  • $\begingroup$ @D.W. I read citeseerx.ist.psu.edu/viewdoc/… which suggested it was NP-hard. But now there is a suggestion below that it isn't. $\endgroup$
    – Simd
    Commented Jun 18, 2014 at 18:11
  • 1
    $\begingroup$ I suggest you edit your question to describe the research you've done, what papers you've found, why those papers are or aren't relevant to your problem, whether you've tried to see whether those results can be extended to your specific problem, etc. Show us what you've tried. Don't just leave this information in the comment threads: comments exist only to help you improve your question. $\endgroup$
    – D.W.
    Commented Jun 18, 2014 at 18:13
  • $\begingroup$ There is quite a literature about this problem, which you'll discover by Googling for 'block edit' operations. An example: Efficient algorithms for the block edit problems. Whether this is the best place to start I don't know, I'm not familiar with the literature, just interested in the problem. $\endgroup$ Commented Aug 23, 2015 at 20:21

1 Answer 1


What it looks like you are after is the Block Swap edit distance. Here is a paper outlining a polynomial time solution to this problem, An Edit Distance Algorithm with Block Swap . I cant recall the exact time complexity they give in the paper, however it is outlined in there.

  • $\begingroup$ I think that is different. I don't want to exactly swap blocks. Here is an example of the fourth type of move in my problem. $P = abcdef \to P' = dabcef$. I don't think this corresponds to any swapping of blocks. $\endgroup$
    – Simd
    Commented Jun 18, 2014 at 16:18
  • $\begingroup$ You have swapped blocks here though, you have swapped the block "abc" with the block "d" any time you move a substring all you are doing is swapping a block of characters, if you move a block forward you are just swapping the block with the group in front of it up until the end of the move, reverse with moving backwards. The example in the paper is a bad one since it is only two blocks in the word. $\endgroup$
    – lPlant
    Commented Jun 18, 2014 at 16:24
  • $\begingroup$ This is true. I suppose this version which is NP-complete has extra operations citeseerx.ist.psu.edu/viewdoc/… . $\endgroup$
    – Simd
    Commented Jun 18, 2014 at 16:39
  • $\begingroup$ Yes, it has block reversals and transformations, which makes it much more complex. $\endgroup$
    – lPlant
    Commented Jun 18, 2014 at 21:11
  • $\begingroup$ Please give references in a robust way, as explained here. Also, please outline the key points so not everybody has to click through. $\endgroup$
    – Raphael
    Commented Aug 23, 2015 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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