编辑距离算法（其中，变化可以对整个子串进行）

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移动的结果。这似乎不太可能，添加重复，变调，并替代容易再次使得它。所以，像莱文斯坦动态规划多项式时间的方法是不太可能的工作。

类似的问题也已在生物信息学下，如“基因组重排”和“移位距离”方面考虑。