日常训练2025-1-3

C. Saraga

rating:1400

https://codeforces.com/problemset/problem/2045/C

思路（Trick ）

题目说至少要将缩写拆分成2个非空子串，我们就思考一下分成两个的情况

假设一个缩写由三部分组成，为：a + b + c

则必须满足，a+b 是 S 的前缀， c 是 T 的后缀，且 a 是 S 的前缀，b+c 是 T 的后缀。可以看出的是，S 和 T 中必须有个相同的部分 b ，为了满足题目要的长度最小的缩写，所以 b 的长度应该为 1 。且 b 位置不在 S 的第一位，因为这样就没有 a 了，同样不能是 T 的最后一位，这样就没有 c 了

所以题目就是让我们在S和T中选一个共有的字符b，找由此字符切分的缩写的最小长度。

做法就是先把 S 串中所有出现过的字符的最左出现位置记录一下，在枚举 T 中的每一个字符，如果在a中出现过则可以快速算出切分出的缩写的大小，最后选一个长度最小的就行。

代码

#include <bits/stdc++.h>

typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 998244353
using i64 = long long;
const int N = 1e5+5;

void solve(){
	std::string s, t;
	std::cin >> s >> t;

	int n = s.size(), m = t.size();

	std::array<int, 26> vis;
	std::fill(vis.begin(), vis.end(), INF);

	for (int i = 1; i < n; i++){
		vis[s[i] - 'a'] = std::min(vis[s[i]-'a'], i);
	}

	int len1 = INF;
	std::array<int, 2> ss{-1, -1};

	for (int i = m - 2; i >= 0; i--){
		if (vis[t[i]-'a'] != INF){
			if (vis[t[i]-'a']+1 + m - i < len1){
				len1 = vis[t[i]-'a']+1 + m - i;
				ss[0] = vis[t[i]-'a'];
				ss[1] = i;
			}
		}
	}

	if (ss[0] == -1){
		std::cout << ss[0] << '\n';
		return;
	}

	std::string ans1 = s.substr(0, ss[0]+1) + t.substr(ss[1]+1, m-ss[1]+1);

	std::cout << ans1 << '\n';
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}