Problem Detail: 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?
Asked By : Lembik
Answered By : lPlant
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/27812 Ask a Question Download Related Notes/Documents
