Inf. Proc. Lett., 51(5), pp.251-255, Sept. 1994,
L. Allison, Dept. Computer Science, Monash University, Australia 3168
Hirschberg gave an alignment algorithm for the
longest common subsequence problem that uses
O(n2)-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.