Constrained string editing
Let X and Y be any two strings of finite length. We consider the problem of transforming X to Y using the edit operations of deletion, insertion, and substitution. The optimal transformation is the one which has the minimum edit distance associated with it. The problem of computing this distance and the optimal transformation using no edit constraints has been studied in the literature. In this paper we consider the problem of transforming X to Y using any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm is presented to compute the minimum distance associated with editing X to Y subject to the specified constraint. The algorithm requires O(|X| | Y|min(| X|,| Y|)) time and space. The technique to compute the optimal transformation is also presented.
Oommen, J. (1986). Constrained string editing. Information Sciences, 40(3), 267–284. doi:10.1016/0020-0255(86)90061-7