## Using Hirschberg's Algorithm to Generate Random Alignments of Strings

#### L. Allison, Information Processing Letters, 51(5), pp.251-255, doi:10.1016/0020-0190(94)90004-3, Sept. 1994

**Abstract**:
Hirschberg gave an alignment algorithm for the
longest common subsequence problem that uses
O(n^{2})-time and O(n)-space for two strings of length ~n.
A simple modification of the algorithm can sample string alignments
at random according to their probability distribution.
This is useful for statistical estimation of evolutionary distances
of a family of strings, e.g., DNA strings.
The algorithm's time and space complexity are unchanged.