70分 求优化

时间复杂度 $O(T×M^2)$ 超时

思路

S1 中找一点插入对应位置的 S2 中的字符
如果和 S2 匹配则为 Yes 否则为 No

例:
S1 : abb
S2 : abaaab
第一次插入
a baa ab ---S2
a|xxx|bb→a|baa|bb 与S2 不符
第二次插入
ab aaa b ---S2
ab|xxx|b→ab|aaa|b 与S2 符和
输出 Yes

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool check(string a,string b){
    if(a==b){return true;}//特判
    ll an=a.length(),bn=b.length();
    for(ll i=0;i<=an;i++){
        string x="";//储存
        //分块
        for(int j=0;j<i;j++){x+=a[j];}                  //a的前半段
        for(int j=0;j<(bn-an);j++){x+=b[i+j];}          //插入
        for(int j=i+(bn-an);j<bn;j++){x+=a[j-(bn-an)];} //a的后半段
        if(b==x){return true;}                          //匹配
    }
    return false;
}
int main(){
    string a,b;ll t,n,m;cin>>t;
    while(t--){
        cin>>n>>m>>a>>b;
        if(check(a,b)){cout<<"Yes\n";}
        else{cout<<"No\n";}
    }
}