Understanding the top-down solution to the longest common substring problem

To solve the longest common substring problem using a top-down dynamic programming approach, we directly implement the recurrence relation using recursion and store previously computed results in a memoization table to avoid redundant work.

The top-down solution

As with any top-down solution, there is a recursive function that solves subproblems and a calling function that initializes the required data structures and triggers the computation. For the longest common substring, we define a single recursive function lcs and a calling function that iterates over all positions to find the global maximum.

The lcs function

The function lcs takes as input an index i into s1, an index j into s2, references to both strings s1 and s2, and a reference to the memoization array memo. The function returns the length of the longest common substring that ends at index i in s1 and index j in s2.

The memo array has dimensions m × n where m is the length of s1 and n is the length of s2, and is initialized with -1 in the calling function, where -1 indicates that the state has not yet been computed. Any non-negative value represents the computed length of the longest common substring ending at that pair of positions.