题解：P13549 热辣滚烫

· · 题解

题解：P13549 热辣滚烫

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

题意简述

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

分析

我们要插入一个字符串，就要把 s_1 分成两个部分。如果满足题目给出的条件，那么这两个部分一定分别是 s_2 的前缀和后缀。

因此，可以转化题目：判断 s_1 和 s_2 的公共前缀和公共后缀是否覆盖了 s_1。

思路

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

代码

#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;
}