# Complexity of edit distance with block operations

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?

• 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.
– D.W.
Jun 18, 2014 at 17:54
• @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. Jun 18, 2014 at 18:11
• 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.
– D.W.
Jun 18, 2014 at 18:13
• 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. Aug 23, 2015 at 20:21

• 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. Jun 18, 2014 at 16:18