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 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.