跳转至

15.4 Longest common subsequence

15.4-1

Determine an \(\text{LCS}\) of \(\langle 1, 0, 0, 1, 0, 1, 0, 1 \rangle\) and \(\langle 0, 1, 0, 1, 1, 0, 1, 1, 0 \rangle\).

\(\langle 1, 0, 0, 1, 1, 0 \rangle\) or \(\langle 1, 0, 1, 0, 1, 0 \rangle\).

15.4-2

Give pseudocode to reconstruct an \(\text{LCS}\) from the completed \(c\) table and the original sequences \(X = \langle x_1, x_2, \ldots, x_m \rangle\) and \(Y = \langle y_1, y_2, \ldots, y_n \rangle\) in \(O(m + n)\) time, without using the \(b\) table.

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
PRINT-LCS(c, X, Y, i, j)
    if c[i, j] == 0
        return
    if X[i] == Y[j]
        PRINT-LCS(c, X, Y, i - 1, j - 1)
        print X[i]
    else if c[i - 1, j] > c[i, j - 1]
        PRINT-LCS(c, X, Y, i - 1, j)
    else
        PRINT-LCS(c, X, Y, i, j - 1)

15.4-3

Give a memoized version of \(\text{LCS-LENGTH}\) that runs in \(O(mn)\) time.

C++
1
2
3
4
5
6
7
8
MEMOIZED-LCS-LENGTH(X, Y, i, j)
    if c[i, j] > -1
        return c[i, j]
    if i == 0 or j == 0
        return c[i, j] = 0
    if x[i] == y[j]
        return c[i, j] = LCS-LENGTH(X, Y, i - 1, j - 1) + 1
    return c[i, j] = max(LCS-LENGTH(X, Y, i - 1, j), LCS-LENGTH(X, Y, i, j - 1))

15.4-4

Show how to compute the length of an \(\text{LCS}\) using only \(2 \cdot \min(m, n)\) entries in the \(c\) table plus \(O(1)\) additional space. Then show how to do the same thing, but using \(\min(m, n)\) entries plus \(O(1)\) additional space.

Since we only use the previous row of the \(c\) table to compute the current row, we compute as normal, but when we go to compute row \(k\), we free row \(k - 2\) since we will never need it again to compute the length. To use even less space, observe that to compute \(c[i, j]\), all we need are the entries \(c[i − 1, j]\), \(c[i − 1, j − 1]\), and \(c[i, j − 1]\). Thus, we can free up entry-by-entry those from the previous row which we will never need again, reducing the space requirement to \(\min(m, n)\). Computing the next entry from the three that it depends on takes \(O(1)\) time and space.

15.4-5

Give an \(O(n^2)\)-time algorithm to find the longest monotonically increasing subsequence of a sequence of \(n\) numbers.

Given a list of numbers \(L\), make a copy of \(L\) called \(L'\) and then sort \(L'\).

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
PRINT-LCS(c, X, Y)
    n = c[X.length, Y.length]
    let s[1..n] be a new array
    i = X.length
    j = Y.length
    while i > 0 and j > 0
        if x[i] == y[j]
            s[n] = x[i]
            n = n - 1
            i = i - 1
            j = j - 1
        else if c[i - 1, j] ≥ c[i, j - 1]
            i = i - 1
        else j = j - 1
    for i = 1 to s.length
        print s[i]
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    m = |X|
    n = |Y|
    if c[m, n] != 0 or m == 0 or n == 0
        return
    if x[m] == y[n]
        b[m, n] = ↖
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y[1..n - 1], c, b) + 1
    else if MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b) ≥ MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)
        b[m, n] = ↑
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b)
    else
        b[m, n] = ←
        c[m, n] = MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)
C++
1
2
3
4
MEMO-LCS-LENGTH(X, Y)
    let c[1..|X|, 1..|Y|] and b[1..|X|, 1..|Y|] be new tables
    MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    return c and b

Then, just run the \(\text{LCS}\) algorithm on these two lists. The longest common subsequence must be monotone increasing because it is a subsequence of \(L'\) which is sorted. It is also the longest monotone increasing subsequence because being a subsequence of \(L'\) only adds the restriction that the subsequence must be monotone increasing. Since \(|L| = |L'| = n\), and sorting \(L\) can be done in \(o(n^2)\) time, the final running time will be \(O(|L||L'|) = O(n^2)\).

15.4-6 \(\star\)

Give an \(O(n\lg n)\)-time algorithm to find the longest monotonically increasing subsequence of a sequence of \(n\) numbers. (\(\textit{Hint:}\) Observe that the last element of a candidate subsequence of length \(i\) is at least as large as the last element of a candidate subsequence of length \(i - 1\). Maintain candidate subsequences by linking them through the input sequence.)

The algorithm \(\text{LONG-MONOTONIC}(A)\) returns the longest monotonically increasing subsequence of \(A\), where \(A\) has length \(n\).

The algorithm works as follows: a new array B will be created such that \(B[i]\) contains the last value of a longest monotonically increasing subsequence of length \(i\). A new array \(C\) will be such that \(C[i]\) contains the monotonically increasing subsequence of length \(i\) with smallest last element seen so far.

To analyze the runtime, observe that the entries of \(B\) are in sorted order, so we can execute line 9 in \(O(\lg n)\) time. Since every other line in the for-loop takes constant time, the total run-time is \(O(n\lg n)\).

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
LONG-MONOTONIC(A)
    let B[1..n] be a new array where every value = ∞
    let C[1..n] be a new array
    L = 1
    for i = 1 to n
        if A[i] < B[1]
            B[1] = A[i]
            C[1].head.key = A[i]
        else
            let j be the largest index of B such that B[j] < A[i]
            B[j + 1] = A[i]
            C[j + 1] = C[j]
            INSERT(C[j + 1], A[i])
            if j + 1 > L
                L = L + 1
    print C[L]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用