一本通-1265：【例9.9】最长公共子序列

【题目描述】 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=，则另一序列Z＝是X的子序列是指存在一个严格递增的下标序列,使得对于所有j=1,2,…,k有：Xij=Zj

例如，序列Z=是序列X=的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X＝和Y＝，则序列是X和Y的一个公共子序列,序列 也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列．因为X和Y没有长度大于4的公共子序列。

给定两个序列X＝和Y=．要求找出X和Y的一个最长公共子序列。

【输入】 共有两行。每行为一个由大写字母构成的长度不超过1000的字符串，表示序列X和Y。

【输出】 第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列．则输出文件仅有一行输出一个整数0。

【输入样例】 ABCBDAB BDCABA

【输出样例】 4

---

#include <bits/stdc++.h>

using namespace std;

string s1, s2;
int m, n;
map<char, vector<int> > um;
vector<int> seq;

int LCS()
{
    int length = seq.size(); if (length == 0) return 0;
    vector<int> d(length + 5);
    d[1] = seq[0];
    int len = 1;
    for (int i = 1; i < length; ++i) {
        int target = seq[i];

        int left = 1, right = len + 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (d[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == len + 1) d[++len] = target;
        else d[left] = target;
    }

    return len;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> s1 >> s2;
    m = s1.size(); n = s2.size();

    for (int i = 0; i < n; ++i) {
        um[s2[i]].push_back(i);
    }

    for (int i = 0; i < m; ++i) {
        if (um.find(s1[i]) != um.end()) {
            vector<int> & v = um[s1[i]];
            int len = v.size();
            for (int j = len - 1; j >= 0; --j) {
                seq.push_back(v[j]);
            }
        }
    }

    cout << LCS() << endl;

    return 0;
}

$n \log n$的解法。比如两个字符串：

abdba
dbaaba

先扫描第一个字符串，取其在第二个字符串中的尾置：

a: 2 3 5 
b: 1 4
d: 0

用每个字母的反序列替换，求最长（严格）上升子序列即可。

替换后为

5 3 2 4 1 0 4 1 5 3 2

首先如果求出一个最长上升子序列，那么这个子序列必然是第二个字符串的子串，因为是按照下标顺序的，求出来的一定严格对应第二个字符串中字符出现的先后顺序。

---

动态规划的解法，对空间优化到$O(n)$。

#include <bits/stdc++.h>

using namespace std;

string s1, s2;
int m, n;
vector<vector<int> > d(2, vector<int>(1005));

int LCS()
{
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                d[i & 1][j] = d[(i - 1) & 1][j - 1] + 1; 
            }
            else {
                d[i & 1][j] = max(d[i & 1][j - 1], d[(i - 1) & 1][j]);
            }
        }
    }

    return d[m & 1][n];
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> s1 >> s2;
    m = s1.size(); n = s2.size();
    cout << LCS() << endl;

    return 0;
}

发现d[i][j]只是和d[i - 1][j - 1], d[i][j - 1], d[i - 1][j]有关，所以可以将空间优化到$O(n)$。

很明显i, i - 1必定是一个奇数，一个偶数，那么很典型的奇偶优化。