题解：P12597 穿睡衣军训

第十次提交题解，求过。

方法

首先考虑暴力，按照子串长度从大到小枚举 $s$ 的所有子串，在判断是不是 $t$ 的子序列，找出符合条件的。虽然不能 AC，但还是可以拿到 $80$ 分的。

这部分代码（赛时代码）

时间复杂度中，用 $n$ 表示 $|s|$，用 $m$ 表示 $|t|$。
时间复杂度：$O(T n^2 m)$。

#include <iostream>
using namespace std;
int T, len;
bool Flag;
string s, t, ans;
bool flag(string s)
{
	int i = 0, j = 0;
	for (; j < t.size(); ++j)
	{
		if (s[i] == t[j])
			i++;
	}
	return (i == s.size());
}
void solve()
{
	cin >> s >> t;
	len = s.size();
	Flag = false;
	for (int i = len; i; --i)
	{
		for (int j = 0; j <= len - i; ++j)
		{
			string S = s.substr(j, i);
			if (flag(S))
			{
				if (Flag) ans = min(ans, S);
				else ans = S, Flag = true;
			}
		}
		if (Flag)
			return cout << ans << endl, void(); 
	}
	cout << endl;
}
int main()
{
	cin >> T;
	while (T--)
		solve();
	return 0;
}

优化1

讲过观察，发现“判断 $s$ 是不是 $t$ 的子序列”的部分，时间复杂度太高了，可以用二分法找出下一个字符的位置，这样可以提高速度，这样子可以把“判断 $s$ 是不是 $t$ 的子序列”的部分从原来的 $O(m)$ 降到 $O(n \log m)$。

代码

这段代码虽然已经优化了，但还是 $80$ 分。 时间复杂度：$O(T n^3 \log m)$。

#include <iostream>
#include <vector>
using namespace std;
int T, len;
bool Flag;
string s, t, ans;
vector <int> num[205];
//其实这个函数可以用 lower_bound 代替
int find(char c, int x)
{
	int l = 0;
	int r = num[c].size() - 1;
	int ans = -1;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (num[c][mid] >= x)
			r = mid - 1, ans = num[c][mid];
		else
			l = mid + 1;
	}
	return ans;
}
bool flag(string s)
{
	for (int i = 0, j = -1; i < s.size(); ++i)
	{
		j = find(s[i], j + 1);
		if (j == -1)
			return false;
	}
	return true;
}
void solve()
{
	cin >> s >> t;
	len = s.size();
	Flag = false;
	for (int i = 'a'; i <= 'z'; ++i)
		num[i].clear();
	for (int i = 0; i < t.size(); ++i)
		num[t[i]].push_back(i);
	for (int i = len; i; --i)
	{
		for (int j = 0; j <= len - i; ++j)
		{
			string S = s.substr(j, i);
			if (flag(S))
			{
				if (Flag) ans = min(ans, S);
				else ans = S, Flag = true;
			}
		}
		if (Flag)
			return cout << ans << endl, void(); 
	}
	cout << endl;
}
int main()
{
	cin >> T;
	while (T--)
		solve();
	return 0;
}

优化2

其实这段枚举子串就用了 $O(n^3)$ 的时间，因为 substr 的时间复杂度是 $O(m)$ 的，其中 $m$ 是子串的长度。所以建议我们在做题中尽量少用 substr（尤其是这种卡时间的题）。
我们继续优化，可以改一个暴力方法：枚举左端点，右端点从左向右枚举，如果把左端点到最后一个加起来，也没有暂时的答案长，就直接结束。如果现在的子串都不行，那加上后面的肯定也不行，也可以直接结束。

AC 代码

终于到代码了。
时间复杂度：$O(T n^2 \log m)$。

#include <iostream>
#include <vector>
using namespace std;
int T, len;
bool Flag;
string s, t, ans;
vector <int> num[205];
int find(char c, int x)
{
	int l = 0;
	int r = num[c].size() - 1;
	int ans = -1;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (num[c][mid] >= x)
			r = mid - 1, ans = num[c][mid];
		else
			l = mid + 1;
	}
	return ans;
}
void solve()
{
	cin >> s >> t;
	len = s.size();
	ans = "";
	Flag = false;
	for (int i = 'a'; i <= 'z'; ++i)
		num[i].clear();
	for (int i = 0; i < t.size(); ++i)
		num[t[i]].push_back(i);
	for (int i = 0; i < len && len - i >= ans.size(); ++i)
	{
		string S = "";
		for (int j = i, k = -1; j < len; ++j)
		{
			k = find(s[j], k + 1);
			if (k == -1)
				break;
			S += s[j];
		}
		if (S.size() == ans.size())
			ans = min(ans, S);
		else if (S.size() > ans.size())
			ans = S;
	}
	cout << ans << endl;
}
int main()
{
	cin >> T;
	while (T--)
		solve();
	return 0;
}

时间复杂度对比

最后改成三段代码的时间复杂度对比。

警示：在处理子串问题时，应优先通过索引操作原字符串，避免频繁创建新对象；同时，利用问题特性（如子序列长度的单调性）设计剪枝条件，减少无效计算。