The recurrence captures the two possibilities for the optimal solution ending at position (i,j): If s1[i-1] == s2[j-1], we extend the LCS of prefixes by one. Otherwise, the optimal solution must omit one of these characters, so we take the max of excluding s1[i-1] (dp[i-1][j]) or excluding s2[j-1] (dp[i][j-1]). By induction, these subproblems are already solved optimally when we compute dp[i][j].

Start from dp[m][n] (bottom-right of table) and trace backwards. When characters match, move diagonally (up-left) and append the character. When they don't match, move in the direction of the larger value (up if dp[i-1][j] > dp[i][j-1], else left). This reconstructs the LCS by reversing the decisions made during table construction.

Both are DP string alignment problems. LCS finds the longest common subsequence, maximizing matches. Edit distance (Levenshtein) finds minimum operations to transform one string to another, minimizing cost. The relationship: edit_distance = |s1| + |s2| - 2 × LCS_length when insertions/deletions cost 1 and substitutions cost 2. They optimize opposite objectives.

Yes, using a rolling array technique. Since each dp[i][j] only depends on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1], we only need the previous row. Maintain two arrays of length n+1 (prev and curr). After processing each row, swap them. This reduces space from O(mn) to O(min(m,n)). The trade-off is that you lose the ability to reconstruct the actual LCS string — only the length is available.

To enumerate all LCS strings, modify the traceback. When both dp[i-1][j] == dp[i][j-1] and they exceed the diagonal value, two valid paths exist. Use backtracking with memoization to collect all distinct LCS strings. The worst-case number of LCS strings is exponential — strings of all identical characters like "AAA" and "AAA" yield C(2n,n) possible LCS strings — so complete enumeration is only practical for small inputs.

The standard O(mn) DP becomes impractical due to both time and memory. A 100K x 100K table requires 10 billion cells. Workarounds exist: use Hirschberg's algorithm for O(min(m,n)) space LCS reconstruction, suffix automaton or bit-parallel techniques for small alphabets, Myers' O(ND) diff algorithm for nearly identical strings, or heuristic approximations when exact LCS is not required.

LCS allows gaps between matched characters; longest common substring (LCSubstr) requires characters to be contiguous in both strings. LCS uses DP with max-over-neighbors: if match: dp[i][j] = dp[i-1][j-1] + 1, else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). LCSubstr resets to zero on a miss: if match: dp[i][j] = dp[i-1][j-1] + 1, else: dp[i][j] = 0. LCSubstr can be solved in O(n+m) with suffix automaton or rolling hash, while LCS is inherently O(mn) in general.

Extend the 2D DP to 3D. When all three characters match, dp[i][j][k] = 1 + dp[i-1][j-1][k-1]. Otherwise take the max of dp[i-1][j][k], dp[i][j-1][k], and dp[i][j][k-1]. Time complexity becomes O(mnp) and space O(mnp). Generalizing to k strings blows up to O(n^k) time, which becomes intractable quickly — multi-string LCS is NP-hard for arbitrary k.

Compute the LCS between two documents (tokenized as sentences, words, or n-grams). The plagiarism ratio is LCS_length / min(|A|, |B|). A high ratio signals significant overlap. In practice: normalize text by removing whitespace and punctuation, use sentence-level tokens for better semantics, combine with shingling and MinHash for large corpora, and set a threshold (e.g., 0.8) to flag potential plagiarism.

Hirschberg's algorithm computes the LCS in O(mn) time but only O(min(m,n)) space while still reconstructing the full LCS string. The trick is divide-and-conquer: compute the DP forward from the start and backward from the end for the middle row, find where forward + backward is maximized to get the split point, then recursively solve the two halves. The significance is that LCS reconstruction doesn't need the full O(mn) DP table — this makes it feasible for large strings where memory is the real bottleneck.

Bit-parallel LCS (Myers algorithm) encodes the DP row as machine words, exploiting parallelism in hardware. For alphabet size Σ, store Σ bitmasks for string B, then use bitwise operations to compute the entire row in O(n/W) where W is the machine word size (e.g., 64 bits). Per-character work drops from O(1) to O(1/W) amortized. This only works for small alphabets where the bitmask fits in a word, and performs best when |B| < W. For Unicode or large alphabets, bitmasks become impractical and you fall back to standard DP.

The Shortest Common Supersequence (SCS) of two strings is the shortest string that has both as subsequences. The connection to LCS is direct: SCS_length = |s1| + |s2| - LCS_length. To build an SCS, run the LCS traceback but interleave non-matching characters from both strings. SCS is essentially the LCS plus the gaps between matched pairs. For more than two strings, SCS stays NP-hard — the same intractability as multi-string LCS.

Normalize both strings before running LCS. For case-insensitive matching, convert both to lowercase (or uppercase) upfront — a one-time O(m+n) cost. For Unicode, NFC/NFD normalization handles characters with diacritics that visually match but have different code points. Consider grapheme clusters (e.g., é as e +́) if visual equality matters. The critical rule: preprocessing must be consistent across both strings before any comparison, never done as a post-check during DP, because the DP recurrence depends on character equality being uniform everywhere.

Git uses a variation of Myers' diff algorithm, which borrows from LCS concepts. When merging branches, git finds the LCS between the original file and each branch version to separate non-conflicting changes from conflicting ones. Segments that differ in only one branch merge automatically; segments changed in both produce merge conflicts. The LCS pinpoints the common base, enabling a three-way merge: changes from the common ancestor to branch A and to branch B are identified independently, then combined. Conflicts only appear where the LCS-based alignment breaks because both branches modified the same region in incompatible ways.

Standard LCS needs both strings in full, but streaming has its workarounds. Keep the current DP row for the first string against the streaming second string, updating it row-by-row as each chunk arrives. The full table never materializes. If the first string also streams in piece by piece, you're dealing with a different problem — true online LCS requires a bounded buffer strategy. When memory is tight, compute LCS on windows or fall back to approximation algorithms like ukkonen's that allow an error threshold ε.

LPS finds the longest subsequence that reads the same forwards and backwards in a single string. The connection: LPS(s) = LCS(s, reverse(s)). Reverse the string and find LCS with the original — the result is the longest palindrome. A palindrome's first and last characters must match, so aligning s with its reverse captures that symmetric structure. Complexity stays O(n²) with O(n) space possible. This relationship shows up in problems like minimum insertions to form a palindrome.

If the first strings share structure (like a common prefix), build a suffix automaton or trie of all first-strings to share DP work. When strings share the same alphabet, pre-compute character positions and reuse row computations. N pairs processed naively take O(N·m·n). You can parallelize at the pair level (each pair is independent) or at the cell level (trickier to sync). If one string is shared across all pairs (e.g., one query against N database entries), build the DP table once and reuse partial results. Sorting pairs by length and processing shortest first helps when using space-optimized O(n) methods.

Hunt-Szymanski is a divide-and-conquer LCS tuned for strings with few matching pairs. First find all matches (positions where s1[i] == s2[j]), then treat these as a DAG longest path problem. Building the full O(m·n) table is wasteful when matches are sparse. Sort match positions by row, then find the longest increasing subsequence in that sorted list. Complexity is O((m+n)·log(m) + R·log(R)) where R is the match count. This beats O(mn) DP when R << mn — which is exactly the scenario git faces with large, divergent files.

Constrained LCS (CLCS) allows up to k mismatched positions without breaking the subsequence. Extend the DP state to dp[i][j][t] = LCS length with exactly t mismatches used so far. On a character match, take the diagonal and optionally reset the mismatch counter. On a miss, either move without counting (free gap) or increment the mismatch counter (counted gap). This runs in O(m·n·k) time with O(m·n) or O(m·n·k) space depending on pruning. When k is small relative to m and n, it's tractable; when k grows large, you're essentially computing string similarity anyway.

Hirschberg maintains two DP rows (forward and backward) instead of the full table. The forward pass goes left to right up to the middle column; the backward pass goes right to left from the end. At the middle row, forward[i][j] + backward[i][j] gives the LCS length crossing that boundary. Find the split point where forward[mid][j] + backward[mid][j] == LCS_length, then recursively reconstruct the LCS string by splitting at that mid point. Standard traceback walks from dp[m][n] backward through the entire O(mn) matrix. Hirschberg achieves O(min(m,n)) space by keeping only two rows at each recursion level — a fundamental difference in how traceback information is stored.