Longest Common Substring

By the end, you can

• Explain the difference between a substring and a subsequence, and why that difference changes the DP recurrence.
• State what dp[i][j] represents and derive the match and mismatch cases from first principles.
• Fill a DP grid by hand for small strings and identify the maximum cell.
• Explain why the reset to zero (not carry-forward) enforces contiguity.
• Recover the longest common substring from the dp grid using the tracked ending index.
• Reduce space usage from O(m·n) to O(min(m,n)) using two rolling rows.
• State the time and space complexity of the DP solution and compare it to the suffix tree approach.
• Name at least two real-world domains where longest common substring appears (e.g., diff tools, bioinformatics).