当前位置:首页 > 洛谷题解 > 高效字符串匹配算法:洛谷P12597题解详解(贪心+二分查找优化)

高效字符串匹配算法:洛谷P12597题解详解(贪心+二分查找优化)

2周前 (06-25)洛谷题解65

截图未命名.jpg 高效字符串匹配算法:洛谷P12597题解详解(贪心+二分查找优化) 字符串匹配 子序列问题 贪心算法 二分查找 C++ 洛谷 第1张

一、问题概述

洛谷P12597题目要求我们找出字符串s中最长的子串,该子串同时是字符串t的子序列。如果有多个相同长度的解,则返回字典序最小的那个。这是一个典型的字符串匹配子序列问题

二、完整代码实现(带注释)

#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; // 当前在t中的匹配位置
    for (char c : sub) {
        auto &vec = pos[c-'a']; // 获取该字符在t中的所有位置
        // 二分查找大于current_pos的最小位置
        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)) { // 检查是否是t的子序列
                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;
}

三、算法解析

1. 预处理阶段

preprocess函数预先处理字符串t,记录每个字符出现的所有位置。这种预处理将字符查找操作的时间复杂度从O(n)降低到O(1),为后续的快速查找奠定基础。

2. 贪心检查策略

check函数实现了核心的贪心算法

  • 按顺序匹配子串的每个字符

  • 每次在t中寻找大于前一个匹配位置的最小位置

  • 使用二分查找(upper_bound)优化查找过程

3. 主求解逻辑

solve函数采用从长到短的贪心策略:

  1. 从可能的最大长度开始检查

  2. 使用滑动窗口遍历所有可能子串

  3. 结合字典序优化,确保找到最优解

  4. 一旦找到解立即返回,避免不必要的计算

四、复杂度分析

  • 时间复杂度:O(n² log m),其中n是s的长度,m是t的长度

  • 空间复杂度:O(m),用于存储t中字符的位置信息

五、优化点

  1. 预处理阶段的哈希表存储

  2. 二分查找替代线性查找

  3. 从长到短的贪心搜索策略

  4. 字典序比较的提前终止


原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

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