@article{mye-86-ndedit,
  author = {Eugene W. Myers},
  title = {An $O(ND)$ Difference Algorithm and Its Variations},
  journal = {Algorithmica},
  volume = {1},
  pages = {251--266},
  year = 1986,
  comment = {Observes that if the costs are 1 for insertion or deletion, 0 for match, and $\geq 2$ for mismatch, then the dynamic programming algorithm for string comparison can be speeded up to $O(ND)$, where $D$ is the cost of the optimum pairing (i.e. the minimum number of insert/delete ops). Not clear whether this result can be extended to more general costs.}
}