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

一、问题概述

洛谷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. 字典序比较的提前终止