Substrings and reconstruction

Questions 1 to 5 of 8

1. 1. What does this program print? ``python def longest(a, b): n = len(a) m = len(b) dp = [0] * (m + 1) best = 0 best_end = 0 for i in range(1, n + 1): for j in range(m, 0, -1): if a[i - 1] == b[j - 1]: dp[j] = dp[j - 1] + 1 if dp[j] > best: best = dp[j] best_end = i else: dp[j] = 0 return f"length = {best} text = {a[best_end - best:best_end]}" print(longest('xabcyz', 'zzabcq')) ``

   length = 2 text = ablength = 3 text = abclength = 3 text = zzabclength = 5 text = xabcy
2. 2. What does this program print? ``python def longest_match(a, b): n = len(a) m = len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[n][m] print(longest_match('abxcdy', 'abcdz')) ``

   2345
3. 3. On a mismatch, the substring method writes 0 into the cell instead of taking the larger neighbour. Why?

   A substring cannot skip letters, so a mismatch ends every run that passed through that cellZero is faster to write than a max callThe neighbours are always 0 at that point in the tableIt makes the answer the last cell of the table
4. 4. The edit distance walk back loops while i > 0 or j > 0. Why not and?

   Because and is slower than or in PythonBecause the two words always have the same lengthBecause the top row of the table has no choices at allBecause a delete moves only i and an insert moves only j, so the walk must go on while either index is above 0
5. 5. What name does the lesson give to the method that keeps only two rows of the value table?

   Type your answer.