Q$2($b$)(14$ marks$)$

Write and test a function longest$\_$common$\_$substring$\_$DP with string arguments left and right, using a top$-$down dynamic programming algorithm, to find the longest common substring of the two strings. It should return the empty string if there is no common substring.

Chapter $23$ shows a variety of dynamic programming approaches to various problems, including the similar $($but different!$)$ problem of the longest common subsequence of two strings.

We would like you to write your function so as to use top$-$down dynamic programming using either a dictionary or a matrix approach for the cache, closely following one of the techniques illustrated in Chapter $23$ for the longest common subsequence problem. You will lose marks if you do not follow an approach similar to Chapter $23.$

Complete the function in the editable code cell below. You can use the same tests that were provided for Question $1($c$)-$ your tutor may use additional tests.

Here is an outline of a possible recursive solution to the problem, similar to the recursive solution to the longest common subsequence problem in Chapter $23.$ This is not exactly the algorithm you need as it does not use cacheing, but it may be a useful start.

#def lc$\_$substring$($left: str$,$ right: str$)->$ str:

#$"""$Return the longest common substring of left and right."""

# if one or both strings are empty:

# return the empty string

# else

# find the LC leading substring of left and right

# compute the LC substring when skipping the right head

# compute the LC substring when skipping the left head

$$

# return the longest of these three substrings

$\%$run $-$i m$269\_$util

$$

$$

def longest$\_$common$\_$substring$\_$DP$($left: str$,$ right: str$)->$ str:

pass # Delete this and replace with your answer here

$$

$$

# Use the same test cases as in Q$1($c$)$

test$($longest$\_$common$\_$substring$\_$DP$,$ longest$\_$common$\_$substring$\_$tests$)$