最长公共子序列（LCS）问题题解

问题分析

本题要求计算两个序列的最长公共子序列（LCS）长度。子序列是指通过删除部分元素（不改变剩余元素相对顺序）得到的序列。

• 输入：两个序列的长度 n、m，以及两个序列 a、b。
• 输出：LCS 的长度。
• 数据范围：1 ≤ n, m, a_i, b_i ≤ 70000，传统的 O(nm) 动态规划会超时，需优化算法。

算法思路

传统的 LCS 动态规划（二维 dp[i][j]）时间复杂度为 O(nm)，无法处理 n, m 达 7e4 的情况。需利用 序列映射 + 最长上升子序列（LIS） 优化，时间复杂度降至 O((n + m) log min(n, m))。

核心原理：

1. 映射转化：若两个序列的 LCS 为 c_1, c_2, ..., c_k，则这些元素在序列 a 中的索引必为递增的（因子序列顺序不变）。因此，可将 LCS 问题转化为 LIS 问题。
2. 具体步骤：
   • 预处理序列 a，记录每个元素的所有索引（按出现顺序存储）。
   • 将序列 b 中的元素替换为其在 a 中的索引（仅保留在 a 中存在的元素），得到新序列 c。
   • 序列 c 的 LIS 长度即为原问题的 LCS 长度（因 LIS 保证索引递增，对应 a 中元素顺序）。

实现细节

1. 预处理索引：用哈希表存储 a 中每个元素的索引列表（递增顺序）。
2. 生成序列 c：对 b 中每个元素，若在 a 中存在，取其所有索引（反向遍历，确保优先选择大索引，优化 LIS 计算）。
3. 计算 LIS：用贪心 + 二分查找维护 tails 数组（tails[i] 表示长度为 i+1 的 LIS 的最小末尾元素），高效计算 LIS 长度。

C++ 代码实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }

    // 预处理a中每个元素的索引列表（递增）
    unordered_map<int, vector<int>> pos;
    for (int i = 0; i < n; ++i) {
        pos[a[i]].push_back(i);
    }

    vector<int> tails;  // 维护LIS的末尾元素数组

    for (int x : b) {
        if (pos.find(x) == pos.end()) {
            continue;  // x不在a中，跳过
        }
        // 反向遍历x在a中的索引列表（优先处理大索引，优化LIS）
        const auto& vec = pos[x];
        for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
            int v = *it;
            // 找tails中第一个 >= v的位置，替换或插入
            auto idx = lower_bound(tails.begin(), tails.end(), v);
            if (idx == tails.end()) {
                tails.push_back(v);
            } else {
                *idx = v;
            }
        }
    }

    cout << tails.size() << endl;

    return 0;
}

复杂度分析

• 时间复杂度：O(n + m * k_avg * log L)，其中 k_avg 是 a 中元素的平均出现次数（总次数为 n），L 是 tails 数组长度（最大为 min(n, m)）。整体可简化为 O((n + m) log min(n, m))，适用于 7e4 规模。
• 空间复杂度：O(n + min(n, m))，用于存储索引列表和 tails 数组。