1
$\begingroup$

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?

$\endgroup$
  • 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. Jun 18 '14 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$ – Lembik Jun 18 '14 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. Jun 18 '14 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$ – reinierpost Aug 23 '15 at 20:21
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Lembik Jun 18 '14 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 Jun 18 '14 at 16:24
  • $\begingroup$ This is true. I suppose this version which is NP-complete has extra operations citeseerx.ist.psu.edu/viewdoc/… . $\endgroup$ – Lembik Jun 18 '14 at 16:39
  • $\begingroup$ Yes, it has block reversals and transformations, which makes it much more complex. $\endgroup$ – lPlant Jun 18 '14 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 Aug 23 '15 at 21:05

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.