編輯距離算法（其中，變化可以對整個子串進行）

Question

是否有當有額外的原語操作，用於確定兩個字符串之間的編輯距離的算法的例子（標準之中插入，刪除，轉置&替代單個字符）它們在整個子字符串上運行。可能的額外的基本操作的實例是：

1）重複的函數 - 其中的副本的任何串，並將其插入在需要的地方

2）移動功能 - 它移動的任何串到一個新位置

使用這些，如果d & d是編輯距離，但d還包括：1）& 2），d（ 「綿羊」， 「SheepBeep」）= 4（如4個插件必須作出），但d（ 「綿羊」，「SheepBeep 「）= 2（插入一個 「B」 然後重複 「EEP」）。類似地，d（ 「CarDog」， 「DogCar」）= 6，但d（ 「CarDog」， 「DogCar」）= 1 2）。

是可以的Levenstein Distance算法，以實現這一目標做出調整，（簡單）的修改？

Answer 1

有隻插入，刪除，並在NP-hard problem移動的結果。這似乎不太可能，添加重複，變調，並替代容易再次使得它。所以，像萊文斯坦動態規劃多項式時間的方法是不太可能的工作。

類似的問題也已在生物信息學下，如「基因組重排」和「移位距離」方面考慮。