题解：CF2094D Tung Tung Sahur

Seraphiel · 2025-05-06 19:35:51 · 题解

题意

判断 s 是否是由 p 的敲击序列产生的。每次操作可以生成一个或两个相同的字符，且生成的字符必须连续。

思路

首先根据题意可知 s 的长度必须在 p 的长度和 2 倍 p 的长度之间，因为每次操作最多可生成两个相同的字符。然后查找 p 中字符在 s 中的对应位置以及是否符合题意。p 的字符在 s 中的对应部分可以是 1 或 2 个相同字符，且必须连续。最后遍历 p 和 s，确保足够对 p 中的字符进行。

code

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        string p,s;
        cin>>p>>s;
        int len1=p.size();
        int len2=s.size();
        if(len2<len1||2*len1<len2){//判断长度 
            cout<<"NO\n";
            continue;
        }
        int i=0,j=0;
        bool flag=1;
        while(i<len1&&j<len2){
            if(s[j]!=p[i]){
                flag=0;
                break;
            }
            int m=len1-i-1;
            int t=min(len2-j-m,2);
            if(t<1){
                flag=0;
                break;
            }
            int op=1;
            if(j+1<len2&&s[j+1]==p[i]&&t>=2){
                op=2;
            }
            j+=op;
            i++;
        }
        if(i==len1&&j==len2&&flag==1){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
    return 0;
}