Mathematica 9 is now available

Wolfram Library Archive


All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Longest Common Subsequence
Author

Sujai Kumar
Organization: University of Illinois at Urbana-Champaign
Department: Beckman Institute
Revision date

2003-09-03
Description

Finds the longest common subsequence in two lists (or two strings).

For example: Both b, a, c and a, b, c are subsequences of the list a, c, b, d, a, c.

And the longest common subsequence of a, c, d, b, a, c and p, c, d, b, d, c is c, d, b, c

This code is based on the description in "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology" by Dan Gusfield.
Subjects

*Mathematics > Discrete Mathematics > Combinatorics
*Science > Biology
Keywords

String matching, longest common subsequence, longest common substring
Downloads Download Wolfram CDF Player

Download
lcs.nb (5.5 KB) - Mathematica Notebook