高效字符串匹配算法:洛谷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
函数采用从长到短的贪心策略:
从可能的最大长度开始检查
使用滑动窗口遍历所有可能子串
结合字典序优化,确保找到最优解
一旦找到解立即返回,避免不必要的计算
四、复杂度分析
时间复杂度:O(n² log m),其中n是s的长度,m是t的长度
空间复杂度:O(m),用于存储t中字符的位置信息
五、优化点
预处理阶段的哈希表存储
二分查找替代线性查找
从长到短的贪心搜索策略
字典序比较的提前终止
原创内容 转载请注明出处