CBMS-2018-12

题目来源：[[做题/文字版题库/CBMS/2018#Question 12|2018#Question 12]] 日期：2024-07-27 题目主题: CS-算法-最长公共子序列

解题思路

我们首先定义 $\alpha [i,j]$ 和 $\beta [i,j]$，并描述它们的递归关系。然后我们计算给定字符串的矩阵 $\alpha$ 和 $\beta$。接着，我们编写伪代码以从矩阵 $\alpha$ 中获取一个最长的公共子序列。最后，我们编写伪代码以在给定矩阵 $\alpha$ 和 $\beta$ 的情况下计算包含 $\mathbf{x}$ 的第 $i$ 个位置的公共子序列的最大长度。

Solution

Part 1: Recurrence Relations

Recurrence for $\alpha [i,j]$

The value of $\alpha [i,j]=l(x_i^p,y_j^p)$ can be computed as follows:

• If $x[i]=y[j]$, then $\alpha [i,j]=\alpha [i-1,j-1]+1$.
• If $x[i]\ne y[j]$, then $\alpha [i,j]=\max (\alpha [i-1,j],\alpha [i,j-1])$.

This can be summarized as:

$$\alpha [i,j]=\{\begin{array}{ll}\alpha [i-1,j-1]+1& \text{if }x[i]=y[j]\\ \max (\alpha [i-1,j],\alpha [i,j-1])& \text{if }x[i]\ne y[j]\end{array}$$

Recurrence for $\beta [i,j]$

The value of $\beta [i,j]=l(x_{n-i+1}^s,y_{m-j+1}^s)$ can be computed as follows:

• If $x[n-i+1]=y[m-j+1]$, then $\beta [i,j]=\beta [i+1,j+1]+1$.
• If $x[n-i+1]\ne y[m-j+1]$, then $\beta [i,j]=\max (\beta [i+1,j],\beta [i,j+1])$.

This can be summarized as:

$$\beta [i,j]=\{\begin{array}{ll}\beta [i+1,j+1]+1& \text{if }x[n-i+1]=y[m-j+1]\\ \max (\beta [i+1,j],\beta [i,j+1])& \text{if }x[n-i+1]\ne y[m-j+1]\end{array}$$

Part 2: Compute Matrices $\alpha$ and $\beta$ for $\mathbf{x}=\text{ACTGG}$ and $\mathbf{y}=\text{ACACG}$

Matrix $\alpha$

Let’s fill the matrix $\alpha$ for $\mathbf{x}=\text{ACTGG}$ and $\mathbf{y}=\text{ACACG}$:

x\y	A	C	A	C	G
A	1	1	1	1	1
C	1	2	2	2	2
T	1	2	2	2	2
G	1	2	2	2	3
G	1	2	2	2	3

Matrix $\beta$

Let’s fill the matrix $\beta$ for $\mathbf{x}=\text{ACTGG}$ and $\mathbf{y}=\text{ACACG}$:

x\y	G	C	A	C	A
G	1	1	1	1	1
G	1	1	1	1	1
T	1	1	1	1	1
C	1	2	2	2	2
A	1	2	3	3	3

Part 3: Pseudocode for Obtaining One of the Longest Common Subsequences

To extract one of the longest common subsequences from the matrix $\alpha$, we use the following algorithm. This algorithm traces back from the bottom-right corner of the matrix to the top-left corner, reconstructing the longest common subsequence by following the path of optimal choices recorded in $\alpha$.

Explanation

• Start from the bottom-right corner of the matrix $\alpha$, i.e., $\alpha [n,m]$.
• Compare characters of $\mathbf{x}$ and $\mathbf{y}$:
  • If $x[i]=y[j]$, include $x[i]$ in the result and move diagonally to $\alpha [i-1,j-1]$.
  • If $x[i]\ne y[j]$, move in the direction that gives the larger value (either up or left).
• Continue this process until reaching the top-left corner of the matrix.
• The result will be one of the longest common subsequences.

Pseudocode

function getLCS(x, y, alpha)
    i = length(x)
    j = length(y)
    lcs = ""
    while i > 0 and j > 0
        if x[i] == y[j]
            lcs = x[i] + lcs
            i = i - 1
            j = j - 1
        else if alpha[i-1, j] >= alpha[i, j-1]
            i = i - 1
        else
            j = j - 1
    return lcs

Part 4: Pseudocode for Computing Maximal Length of Common Subsequences Containing the $i$-th Position of $\mathbf{x}$

Given matrices $\alpha$ and $\beta$, we can compute the maximal length of common subsequences that include the $i$-th position of $\mathbf{x}$. This is done by evaluating the length of subsequences that start from the beginning and end at the $i$-th position, combined with subsequences that start at the $i$-th position and extend to the end.

Explanation

• For each position $j$ in $\mathbf{y}$:
  • Combine the length of the prefix up to $i$ ($\alpha [i,j]$) with the length of the suffix from $i$ onwards ($\beta [n-i+1,m-j+1]$) as the length of the common subsequence.
  • If $x[i]=y[j]$, since $x[i]$ is included in both the prefix and suffix, subtract 1 from the total length.
• The maximum value obtained through this process gives the desired length.

Pseudocode

function maxLengthWithPosition(x, y, alpha, beta, i)
    maxLength = 0
    for j = 1 to length(y)
        currentLength = alpha[i, j] + beta[n-i+1, m-j+1]
        if x[i] == y[j]
            currentLength = currentLength - 1
        maxLength = max(maxLength, currentLength)
    return maxLength

知识点

动态规划最长公共子序列递归

难点思路

对于递归关系的理解和矩阵填充的具体实现可能会比较复杂，需要仔细考虑每一步的递推关系。

解题技巧和信息

• 动态规划表格填充方法：先初始化，然后按照递推关系逐步填充。
• 递归关系需要对字符串字符的匹配情况进行详细考虑，以确保递推关系的正确性。

重点词汇

• common subsequence 公共子序列
• recurrence relation 递推关系
• prefix 前缀
• suffix 后缀
• dynamic programming 动态规划

参考资料

1. Introduction to Algorithms, 3rd Edition, Cormen et al., Chapter 15.