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

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

2个月前 (07-10)

洛谷P12597题解:子序列查找的贪心与二分优化详解  贪心算法 二分查找优化 子序列匹配 第1张

一、题目解读

洛谷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;
}

五、总结

该解法通过预处理与二分查找大幅优化了子序列匹配的效率,结合贪心策略避免冗余计算。时间复杂度O(nlogn),适用于处理大规模字符串。代码简洁且易于理解,在洛谷等平台可通过多数测试案例,是解决此类问题的典型范例。

参考:洛谷P12597题解

原创内容 转载请注明出处

分享给朋友:

相关文章

力扣1221:一次扫描解决分割平衡字符串 时间O(n)空间O(1)

力扣1221:一次扫描解决分割平衡字符串 时间O(n)空间O(1)

题目重解给定一个仅包含'L'和'R'的字符串,要求将其分割成尽可能多的子串,且每个子串中'L'和'R'的数量相等。例如输入"R...

牛客13271题「删除K个数字的最小数」解题报告:贪心算法与栈的应用(附代码注释)

牛客13271题「删除K个数字的最小数」解题报告:贪心算法与栈的应用(附代码注释)

一、题目解读牛客13271题要求从给定的数字字符串中删除K个数字,使得剩余数字按原顺序排列后得到的最小数。题目核心在于如何在保持数字相对顺序的前提下,通过删除操作得到最优解。需注意结果字符串可能包含前...

力扣LCR074题区间合并算法解析:贪心排序与区间重叠处理

力扣LCR074题区间合并算法解析:贪心排序与区间重叠处理

一、题目解读力扣LCR074题要求对给定的二维区间数组(每个区间由起始点和终止点构成)进行合并,将重叠的区间合并为更宽的区间,最终输出不重叠的合并结果。例如,输入[[1,3],[2,6],[8,10]...

力扣1643题:第K小字典序路径(附C++代码与解题思路)

力扣1643题:第K小字典序路径(附C++代码与解题思路)

一、题目解读本题要求生成从原点(0, 0)到目标坐标(destination[0], destination[1])的路径中,字典序第K小的路径。路径仅由向下字符'V'(代表垂直移动)...

洛谷P3817题解:基于贪心算法的糖果分配优化策略

洛谷P3817题解:基于贪心算法的糖果分配优化策略

一、题目解读洛谷P3817题目要求处理n个盒子中的糖果分配问题:给定每个盒子的糖果数a[i]及限制值x,需通过吃掉部分糖果,确保任意相邻盒子(a[i-1] + a[i])的总和不超过x。输出最小需吃掉...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。