ITPEC FE Subject B October 2024 Question 7

Topic: String Processing

From the answer group below, select the correct combination of answers to be inserted into A and B in the program.

Given two strings, str1 and str2, the task is to determine the length of the longest common subsequence (LCS), that is, the length of the longest subsequence present in both strings. For instance, if str1 is “ABXDZ” and str2 is “ABCD”, the LCS between str1 and str2 will be “ABD” and the length of the LCS will be 3.
The function lcs(string: str1, string: str2, integer: m, integer: n) takes two strings str1 and str2 and two integers m and n as arguments. str1 and str2 are the strings on which the length of the LCS is calculated. m and n are indexes addressing the target characters in str1 and str2, respectively. On the first call, m and n represent the lengths of str1 and str2, respectively. The function returns an integer containing the value of the length of the LCS of str1 and str2. For instance, the function may be called as lcs("ABXDZ", "ABCD", 5, 4).
Another function max(integer: a, integer: b) is also used. The function takes two integers a and b as arguments. It compares these two integers and returns the integer value of whichever is the maximum between a and b.

[Program]
○ integer: max(integer: a, integer: b)
if (a > b)
return a
else
return b
endif
○ integer: lcs(string: str1, string: str2, integer: m, integer: n)
if (m = 0 or n = 0)
return 0
endif
if (the m-th character of string str1 = the n-th character of string str2)
return 1 + lcs(str1, str2, m - 1, n - 1)
else
return max(lcs(str1, str2, m, A),
lcs(str1, str2, m - 1, B))
endif

Answer group

OptionAB

Explanation

A: n - 1, B: n — on a mismatch, drop the last character of one string at a time: from str2 in the first call, from str1 in the second.

When the m-th character of str1 and the n-th character of str2 differ, they cannot both end the common subsequence, so at least one of them is discarded. The LCS is the larger of two smaller problems: str1 whole against str2 without its last character, lcs(str1, str2, m, n - 1) (blank A), and str1 without its last character against str2 whole, lcs(str1, str2, m - 1, n) (blank B). Each call shrinks one index by 1, so the recursion reaches the base case m = 0 or n = 0.

Example: in lcs("ABXDZ", "ABCD", 5, 4), Z and D differ, so the result is the larger of the LCS of ABXDZ and ABC (2, "AB") and the LCS of ABXD and ABCD (3, "ABD"), which is 3.

Answer (c)

Why not others:

  • •(a) and (b) — A as n makes the first call lcs(str1, str2, m, n), the same arguments as the current call, so the recursion never ends; in addition (a)'s B drops both characters at once and (b)'s B steps past the end of str2
  • •(d) — A is right, but B as n + 1 points beyond the end of str2 instead of keeping it whole
  • •(e) and (f) — A as n + 1 points beyond the end of str2 on the very first call and moves away from the base case n = 0 instead of towards it

Key rule: Every recursive call must shrink the problem toward the base case; in LCS the mismatch case tries both "drop one last character" subproblems and keeps the larger result.

String Processing · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.