Understanding the longest common subsequence problem

Many times when building software, the problem we're really solving is comparison. A diff tool shows a developer what changed between two versions of a file, and a spell checker figures out the closest match to a misspelt word, while a plagiarism detector finds overlapping passages between two documents.

In all these cases, the core challenge is the same: given two sequences, find out what they share. A fundamental problem in this space is the longest common subsequence problem, where the goal is to find the longest sequence of elements that appears in the same relative order in both input sequences.