国网_网络图片制作公司_东莞网络优化服务商_网游推广员

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

762C - Two strings

---

二、解题报告

1、思路分析

考虑合法方案：

去除掉b的一个子串后，b剩下的前缀和后缀一定分别是a的前缀和后缀的子序列

我们前后缀分离：

构建长度为 n 的两个数组 pre 和 suf

suf[i] 代表 a[i::] 能包含最长的 b[suf[i]::]

pre[] 代表 a[:i] 能包含的最长的 b[:pre[i]]

那么我们需要删除的最短长度就是 min{ suf[i + 1] - pre[i] - 1 }

本题要输出方案，那么维护下前缀长度和后缀起始位置即可

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int P = 1E9 + 7;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;void solve() {std::string a, b;std::cin >> a >> b;int n = a.size(), m = b.size();std::vector<int> suf(n + 1, m);for (int i = n - 1, j = m - 1; ~i; -- i) {if (a[i] == b[j]) {-- j;}if (j < 0) {std::cout << b << '\n';return;}suf[i] = j + 1;}int mi = suf[0], mii = -1, len = 0;for (int i = 0, j = 0; i < n; ++ i) {if (a[i] == b[j]) {++ j;if (mi > suf[i + 1] - j)mi = suf[i + 1] - j, mii = i, len = j;}}if (mi == m) {std::cout << "-\n";}else {std::cout << b.substr(0, len);if (suf[mii + 1] < m)std::cout << b.substr(suf[mii + 1]) << '\n';}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint cur = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - cur << '\n';
#endifreturn 0;
}