当前位置：首页 > 洛谷 > 洛谷P12597题解：子序列查找的贪心与二分优化详解

洛谷P12597题解：子序列查找的贪心与二分优化详解

4个月前 (07-10)

一、题目解读

洛谷P12597题目要求在一个字符串s中寻找最长的子序列，该子序列需满足字符顺序与另一个字符串t相同。题目强调子序列无需连续，但字符相对位置需保持一致。例如，若t为"abc"，则s中的"axbycz"符合条件，而"acb"不符合。解题需高效处理字符顺序与位置关系，属于算法优化类问题。

二、解题思路

采用“贪心+二分查找”策略：

1. 预处理位置信息：构建哈希表记录t中每个字符的索引位置，便于快速定位。

2. 贪心策略：从最长可能长度开始向下遍历，优先检查字典序较小的子串，避免重复计算。

3. 二分查找优化：在检查子序列时，通过二分定位下一个字符的合法位置，降低时间复杂度。

三、解题步骤

1. 预处理t：函数preprocess()遍历t，将每个字符的位置存入对应字母的向量中（如'a'的位置存入pos[0]）。

2. 子序列检查：check()函数通过二分查找确认每个字符在s中是否存在合法位置，维持相对顺序。

3. 滑动窗口求解：外层循环从最大长度递减，内层滑动窗口遍历s，提取子串并检查：

若当前子串字典序大于已有解，直接跳过（贪心剪枝）。

若通过检查，更新解并判断是否已达最大长度，提前终止。

四、代码与注释

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 预处理t中每个字符的位置，使用哈希表存储
vector<vector<int>> preprocess(const string &t) {
    vector<vector<int>> pos(26); // 26个字母的位置列表
    for (int i = 0; i < t.size(); ++i) {
        pos[t[i]-'a'].push_back(i); // 记录字符位置
    }
    return pos;
}

// 使用贪心+二分查找优化子序列检查
bool check(const string &sub, const vector<vector<int>> &pos) {
    int current_pos = -1; // 上一个字符的位置
    for (char c : sub) {
        auto &vec = pos[c-'a']; // 当前字符的位置列表
        auto it = upper_bound(vec.begin(), vec.end(), current_pos); // 二分查找下一个合法位置
        if (it == vec.end()) return false; // 不存在合法位置
        current_pos = *it; // 更新位置
    }
    return true;
}

string solve(const string &s, const string &t) {
    auto pos = preprocess(t); // 预处理t的位置
    int n = s.size(), m = t.size();
    string result;
    
    // 从可能的最大长度开始检查
    for (int len = min(n, m); len >= 1; --len) {
        // 滑动窗口检查所有长度为len的子串
        for (int i = 0; i + len <= n; ++i) {
            string sub = s.substr(i, len);
            // 提前终止条件：字典序更小的解不会被覆盖
            if (!result.empty() && sub >= result) continue;
            if (check(sub, pos)) {
                if (result.empty() || sub < result) {
                    result = sub;
                    // 找到最长解后立即返回
                    if (len == min(n, m)) return result;
                }
            }
        }
        if (!result.empty()) return result;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        string s, t;
        cin >> s >> t;
        cout << solve(s, t) << '\n';
    }
    return 0;
}