专栏文章

题解：P13549 热辣滚烫

FFake_Cry
P13549题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minnrqwi
此快照首次捕获于
2025/12/02 05:25
3 个月前
此快照最后确认于
2025/12/02 05:25
3 个月前
查看原文

题解：P13549 热辣滚烫

本题考查对字符串的操作。

题意简述

对于每组数据，题目给定两个字符串 s1s_1 和 s2s_2，求能否在 s1s_1 中间插入任意字符串得到 s2s_2。

分析

我们要插入一个字符串，就要把 s1s_1 分成两个部分。如果满足题目给出的条件，那么这两个部分一定分别是 s2s_2 的前缀和后缀。
因此，可以转化题目：判断 s1s_1 和 s2s_2 的公共前缀和公共后缀是否覆盖了 s1s_1。

思路

分别从前后遍历两个字符串。第一次从前开始扫，记录公共前缀的长度；第二次从后开始扫，记录公共后缀的长度。根据分析，如果公共前缀的长度和公共后缀的长度之和大于 s1s_1 的长度，即覆盖了 s1s_1，那么满足条件。

代码

CPP
#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int n,m;
	cin>>n>>m;
	string a,b;
	cin>>a>>b;
	int i=0,j=0;//两个变量记录公共前后缀的长度
	while(a[i]==b[i]) i++;//使用 while 循环，若不满足括号里的条件就退出
	int x=n-1,y=m-1;//从后开始扫
	while(a[x]==b[y]){
		if(x<0||y<0) break;
		x--,y--;
		j++;
	}
	if(i+j>=n) cout<<"Yes\n";//覆盖
	else cout<<"No\n";//没覆盖
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	int _=1; cin>>_;//多组数据强烈建议使用函数处理
	while(_--) solve();
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...