Longest common subsequence: Difference between revisions
m
Restored recent References edit.
m (Specified the (<>) relation over matches.) |
m (Restored recent References edit.) |
||
Line 2:
Define a subsequence to be any string obtained by deleting zero or more symbols from an input string.
The
Let A = A[0]… A[m-1] and B = B[0]… B[n-1], m <= n be strings drawn from an alphabet '''Σ''' of size s, containing every distinct symbol in A + B.
Line 38:
'''References'''
# "A linear space algorithm for computing maximal common subsequences" by Daniel S. Hirschberg, published June 1975
# "An Algorithm for Differential File Comparison" by James W. Hunt and M. Douglas McIlroy, June 1976
# "A Fast Algorithm for Computing Longest Common Subsequences" by James W. Hunt and Thomas G. Szymanski, published May 1977
# "Simple and fast linear space computation of longest common subsequences" by Claus Rick, received 17 March 2000, Information Processing Letters,
▲"An Algorithm for Differential File Comparison" by James W. Hunt and M. Douglas McIlroy, June 1976<br />
<br />
▲"A Fast Algorithm for Computing Longest Common Subsequences" by James W. Hunt and Thomas G. Szymanski, published May 1977<br />
▲"Simple and fast linear space computation of longest common subsequences" by Claus Rick, received 17 March 2000, Information Processing Letters,<br />
'''Examples'''
| |||