Data Structures and Algorithms: Longest Common Subsequence

Data Structures and Algorithms

Longest Common Subsequence

Another problem that has a dynamic solution is that of finding the longest common subsequence.

Problem

Given two sequences of symbols, X and Y, determine the longest subsequence of symbols that appears in both X and Y.

Reference

Cormen, Section 16.3
Lecture notes by Kirk Pruhs, University of Pittsburgh
Pseudo-code from John Stasko's notes for CS3158 at Georgia Tech

Key terms

optimal sub-structure
a property of optimisation problems in which the sub-problems which constitute the solution to the problem itself are themselves optimal solutions to those sub-problems. This property permits the construction of dynamic algorithms to solve the problem.