描述 Description

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Clarification

What's the definition of Longest Common Subsequence?

如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子序列，则输出它们的长度4，并打印任意一个子序列。

Example

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

[lintcode Longest Common Subsequence]

分析 Analysis

lcs最优子结构

最长公共子序列的结构有如下表示：

设序列X=&lt;x1, x2, …, xm&gt;和Y=&lt;y1, y2, …, yn&gt;的一个最长公共子序列Z=&lt;z1, z2, …, zk&gt;，则：

若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；

若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；

若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=<x1, x2, …, xm-1>，Yn-1=<y1, y2, …, yn-1>，Zk-1=<z1, z2, …, zk-1>。

lcs最优子结构证明

记:

Xi=﹤x1，⋯，xi﹥即X序列的前i个字符 (1≤i≤m)（前缀）

Yj=﹤y1，⋯，yj﹥即Y序列的前j个字符 (1≤j≤n)（前缀）

假定Z=﹤z1，⋯，zk﹥∈LCS(X , Y)。

若xm=yn（最后一个字符相同），则不难用反证法证明：该字符必是X与Y的任一最长公共子序列Z（设长度为k）的最后一个字符，即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时，问题化归成求Xm-1与Yn-1的LCS（LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1）。
若xm≠yn，则亦不难用反证法证明：要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立，若zk≠xm则有Z∈LCS(Xm-1 , Y)，类似的，若zk≠yn 则有Z∈LCS(X , Yn-1)。此时，问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为：max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。

lcs最优值

c[i,j]表示xi和yj的lcs长度最优值。如果只是输出最优值，可以只使用一个2*更小长度那个字符串长度的数组保存，因为数组元素c[i,j]的值仅由c[i-1,j-1]，c[i-1,j]和c[i,j-1]三个值之一确定。且时间复杂度仍然是Ο(m+n)。

lcs最优解

输出最优解可以加上一个辅助数组b，但是也可以直接使用c[i,j]和原两个数组构建最优解输出。

算法复杂度分析

时间复杂度：最优值和最优解时间分别是Ο(mn)和Ο(m+n)。

空间Ο(mn)，因为即使不使用辅助数组b, c仍需要Ο(mn)的空间。

[算法导论3th]

[动态规划算法解最长公共子序列LCS问题]

代码 Code

int longestCommonSubsequence0(string A, string B) {
    /*
     * 仅输出lcs最优值
     */
    unsigned long la = A.length();
    unsigned long lb = B.length();
    unsigned long l_min = la <= lb ? la : lb;
    unsigned long l_max = la > lb ? la : lb;
    int *opt = new int[l_min + 1]();
    string min_p, max_p;
    if (l_min == la) {
        min_p = A;
        max_p = B;
    } else {
        min_p = B;
        max_p = A;
    }

    int old, tmp;
    for (int i = 1; i <= l_max; i++) {
        old = 0;
        for (int j = 1; j <= l_min; j++) {
            tmp = opt[j];
            if (max_p[i - 1] == min_p[j - 1])
                opt[j] = old + 1;
            else
                opt[j] = max(opt[j], opt[j - 1]);
            old = tmp;
        }
    }
    return opt[l_min];
}

#include <iostream>

using namespace std;

void printLCS(string A, string B, int i, int j, int **opt);

int longestCommonSubsequence(string A, string B) {
    /*
     * 输出lcs最优值和最优解
     */
    unsigned long la = A.length() + 1;
    unsigned long lb = B.length() + 1;
    int **opt = new int *[la];
    for (int i = 0; i < la; i++)
        opt[i] = new int[lb]();
//    int opt[la][lb] = {};
    for (int i = 1; i < la; i++)
        for (int j = 1; j < lb; j++) {
            if (A[i - 1] == B[j - 1])
                opt[i][j] = opt[i - 1][j - 1] + 1;
            else
                opt[i][j] = max(opt[i - 1][j], opt[i][j - 1]);
        }
    printLCS(A, B, (int) A.length(), (int) B.length(), opt);
    cout << endl;
    return opt[la - 1][lb - 1];
}

void printLCS(string A, string B, int i, int j, int **opt) {
    /*
     * 输出lcs最优解
     */
    if (i <= 0 || j <= 0)
        return;

    if (A[i - 1] == B[j - 1]) {
        printLCS(A, B, i - 1, j - 1, opt);
        cout << A[i - 1];
    } else if (opt[i - 1][j] >= opt[i][j - 1])
        printLCS(A, B, i - 1, j, opt);
    else
        printLCS(A, B, i, j - 1, opt);
}

int main() {
    string A = "ABCBDAB", B = "BDCABA";
//    string A = "B", B = "A";
    cout << longestCommonSubsequence0(A, B) << endl;
    cout << longestCommonSubsequence(A, B) << endl;
    return 0;
}

最长公共子序列Longest Common Subsequence (LCS) [**]