The paper presents a linear space algorithm for computing the longest common subsequence (LCS) of two strings, which is a problem that has traditionally been solved in quadratic time and space. The author, D.S. Hirschberg from Princeton University, introduces an algorithm that operates in quadratic time but uses linear space, making it more efficient for large strings. The problem is defined as finding a string \( C \) that is a common subsequence of two given strings \( A \) and \( B \), with the goal of maximizing the length of \( C \). The algorithm is described in detail, including its correctness proof and time-space analysis. Two versions of the algorithm are presented: Algorithm A, which uses a matrix to store intermediate results, and Algorithm B, which uses a vector to store results, reducing space complexity. The paper also includes a theorem that helps in finding the maximal common subsequence by dividing the problem into smaller subproblems. This theorem is used to develop Algorithm C, which recursively solves the problem until it reaches a trivial subproblem. Algorithm C is proven to be correct and analyzed for its time and space complexity, showing that it operates in \( O(mn) \) time and \( O(m+n) \) space. Finally, the paper discusses how Algorithm C can be modified to find the edit distance between two strings, providing a practical application of the algorithm.The paper presents a linear space algorithm for computing the longest common subsequence (LCS) of two strings, which is a problem that has traditionally been solved in quadratic time and space. The author, D.S. Hirschberg from Princeton University, introduces an algorithm that operates in quadratic time but uses linear space, making it more efficient for large strings. The problem is defined as finding a string \( C \) that is a common subsequence of two given strings \( A \) and \( B \), with the goal of maximizing the length of \( C \). The algorithm is described in detail, including its correctness proof and time-space analysis. Two versions of the algorithm are presented: Algorithm A, which uses a matrix to store intermediate results, and Algorithm B, which uses a vector to store results, reducing space complexity. The paper also includes a theorem that helps in finding the maximal common subsequence by dividing the problem into smaller subproblems. This theorem is used to develop Algorithm C, which recursively solves the problem until it reaches a trivial subproblem. Algorithm C is proven to be correct and analyzed for its time and space complexity, showing that it operates in \( O(mn) \) time and \( O(m+n) \) space. Finally, the paper discusses how Algorithm C can be modified to find the edit distance between two strings, providing a practical application of the algorithm.