Longest Common Subsequence (LCS)

LCS exhibits optimal substructure, meaning the optimal solution to the full problem can be constructed efficiently from optimal solutions to its subproblems. If the last characters of two sequences match, that character is part of the LCS, and the problem reduces to finding the LCS of the remaining prefixes. If they differ, the LCS is the longer of two options: skipping the last character of the first sequence or skipping the last character of the second. This recursive decomposition is what makes the dynamic programming solution possible.

A naive recursive implementation of LCS has exponential time complexity O(2^n) because it recomputes the same subproblems repeatedly. The LCS of two prefixes is needed multiple times across different recursive branches. Dynamic programming eliminates this redundancy by storing results in a memoization table. For sequences of length m and n, a standard DP approach fills an (m+1) × (n+1) matrix, reducing time complexity to O(mn). This property is why LCS is the textbook example for introducing DP.

A critical distinction: an LCS is a subsequence, not a substring. Characters must appear in the same relative order but do not need to be contiguous. For example, given AXY and AYX, the LCS is AX or AY (length 2), not XY. This non-contiguity is what makes LCS ideal for diff algorithms—it can skip over unchanged boilerplate to find the essential structural alignment between two document versions, even when new text is inserted in the middle of a paragraph.

The DP table alone only yields the length of the LCS. To produce the actual diff, a backtracking phase traces from the bottom-right cell back to the origin. Each move corresponds to an edit operation:

• Diagonal move: characters match (unchanged line)
• Up move: deletion from the first document
• Left move: insertion from the second document This backtrack produces the minimal edit script that transforms one document into the other, which is the foundation of the Unified Diff Format and legal redline generation.

For any given pair of sequences, there may be multiple distinct LCS solutions of the same maximal length. For instance, ABC and ACB have two LCS results: AB and AC. This ambiguity matters in legal differencing because different valid alignments can produce semantically different redlines. Production systems often apply tie-breaking heuristics—such as preferring matches that preserve clause boundaries or align defined terms—to ensure the generated diff is legally coherent and not just mathematically minimal.

The classic DP approach requires O(mn) space to store the entire matrix, which becomes prohibitive for large legal documents. Hirschberg's algorithm reduces space complexity to O(min(m, n)) while maintaining O(mn) time. It uses a divide-and-conquer strategy: find the optimal midpoint of the alignment, recursively solve the left and right halves, and combine. This optimization is critical for comparing multi-hundred-page contracts without exhausting memory, making LCS viable in production legal AI pipelines.

A quantitative metric measuring the minimum number of single-character operations (insertions, deletions, substitutions) required to transform one string into another. While LCS focuses on the preserved sequence, edit distance focuses on the cost of change. The relationship is direct: EditDistance = |A| + |B| - 2 * |LCS(A, B)|.

• Use Case: Fuzzy string matching and spell-checking.
• Contrast: LCS finds commonality; Levenshtein measures difference.

An O(ND) greedy algorithm that finds the shortest edit script between two sequences by exploring an edit graph. It is the foundational algorithm behind the standard Unix diff utility and directly relies on LCS logic to produce a minimal, human-readable patch.

• Mechanism: Traverses a grid to find the shortest path from the top-left to bottom-right corner.
• Output: A minimal set of insertions and deletions, which is the inverse of the LCS.

A text comparison method that decomposes documents into contiguous sequences of 'n' words or characters and measures their overlap. Unlike LCS, which requires strict sequential order, n-gram similarity can detect paraphrased or reordered content.

• Jaccard Index: A common metric for measuring n-gram set overlap.
• Advantage: More robust to block-level reordering than strict LCS.

A technique that identifies non-identical but similar strings across documents. It is crucial for aligning moved or reworded clauses that a strict LCS-based text comparison would miss. Fuzzy matching often uses edit distance or token-based ratios.

• Example: Matching 'The Purchaser shall indemnify' with 'The Buyer agrees to indemnify'.
• Application: Pre-processing step before running a semantic or structural diff.

The process of creating a compact, machine-readable file containing only the differences between two documents. The LCS is the theoretical backbone for generating a minimal patch. The patch file stores the instructions (insertions and deletions) needed to transform the original into the modified version.

• Formats: Unified Diff Format, Context Diff.
• Function: patch(original, diff_script) = modified.

An algorithm measuring the minimum-cost sequence of node insertions, deletions, and relabelings to transform one hierarchical structure into another. This extends LCS from a flat sequence problem to a structured, ordered tree problem, essential for comparing XML or Abstract Syntax Trees (ASTs).

• Zhang-Shasha Algorithm: A classic solution for ordered tree edit distance.
• Legal Use: Comparing the logical structure of contract clause hierarchies.