The Number of Distinct Alignments of Two Strings
Michael A. Covington · Journal of Quantitative Linguistics · 2004
An alignment is a way of pairing up elements of two strings, optionally skipping some elements but preserving the order. This paper presents formulae for the number of distinct alignments of two strings, using various critera of distinctness. These numbers are of interest because they give the size of the search space for inexact string matching, DNA sequence alignment, and the first step in comparative reconstruction of ancient languages.