题解：P13549 热辣滚烫

LotleTos · 2025-10-02 17:48:13 · 题解

题意

给出两个字符串 s_1、s_2，问能否在 s_1 中间插入任意字符串，得到 s_2。

思路

插入的位置把 s_1 分成了前后两个部分，很明显，这两个部分分别是 s_2 的前缀和后缀。

所以题目可以转化成：求 s_1 和 s_2 的公共前后缀是否覆盖了整个 s_1。

分别从前往后和从后往前遍历两个字符串，计算出公共前缀的长度和公共后缀的长度，如果两个长度相加大于等于 s_1 的长度，就说明公共前后缀覆盖了整个 s_1，输出 Yes，否则输出 No。

代码

#include<bits/stdc++.h>
using namespace std;
int f(){
    int n,m;
    cin>>n>>m;
    string a,b;
    cin>>a>>b;
    int sum1,sum2=0;
    for(sum1=0;sum1<n;sum1++){
        if(a[sum1]!=b[sum1]){
            break;
        }
    }
    for(int a1=n-1,a2=m-1;a1>=0&&a2>=0;a1--,a2--){
        if(a[a1]==b[a2]){
            sum2++;
        }
        else{
            break;
        }
    }
    if(sum1+sum2>=n){
        cout<<"Yes\n";
    }
    else{
        cout<<"No\n";
    }
    return 0;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        f();
    }
}