LCS Theory

1. Recurrence

if A[i-1] == B[j-1]:
  dp[i][j] = 1 + dp[i-1][j-1]
else:
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2. Complexity

• Time: O(m×n)
• Space: O(m×n) → O(min(m,n)) for length only
• Reconstruction needs full or directional info.

3. Reconstruction Strategy

Start bottom-right, move diagonally on match, else move to the larger predecessor.

4. Variants

• Longest Common Substring (reset to 0 on mismatch).
• Shortest Common Supersequence (length m+n-LCS).
• Diff / patch generation (store operations).