Wolfram Library Archive

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

Longest Common Subsequence

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


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.

*Mathematics > Discrete Mathematics > Combinatorics
*Science > Biology

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

lcs.nb (5.5 KB) - Mathematica Notebook