[CF2164D] Copy String 题解

从右向左尝试让

t_i

匹配

s

中的一个字符。显然匹配到的

x_i

要先满足

s_{x_i}=t_i,x_i\le i

。同时为了让已经放好的

t_i

不被其他字符覆盖，

[x_i,i]

这个区间不能被其他区间包含，即

x_i\le x_{i+1}

。直接拿一个指针扫即可。于是得到

s

中每个字符最终的位置

\text{to}_i

。

对于每个

s_i

，每次操作就将这个字符往右移动一格，直到移动到

\text{to}_i

。每次操作没有确定的部分就直接从前一次操作复制下来即可。

时间复杂度

\mathcal{O}(nk_{\max})

。

注意这个实现并没有拿指针扫。

code

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=1000007,ee=1e18,p=998244353;
ll n,k,c,to[maxn];
string S,T,ans[maxn];
vector<ll> vec[26];
void chmax(ll &a,ll b){a=max(a,b);}
void solve(void){
    for(ll i=0;i<26;i++) vec[i].clear();
    for(ll i=1;i<=n;i++) to[i]=0,vec[S[i]-'a'].pb(i);
    ll mx=n+1;
    for(ll i=n,ch;i>=1;i--){
        ch=T[i]-'a',mx=min(mx,i);
        for(;!vec[ch].empty()&&vec[ch].back()>mx;) vec[ch].pob();
        if(vec[ch].empty()) return cout<<"-1\n",void();
        chmax(to[vec[ch].back()],i),mx=min(mx,vec[ch].back());
    }
    c=0;
    for(ll i=1;i<=n;i++) c=max(c,to[i]-i);
    if(c>k) return cout<<"-1\n",void();
    if(c==0) return cout<<"0\n",void();
    for(ll i=1;i<=c;i++) ans[i].clear(),ans[i].resize(n+1,'$');
    for(ll i=n;i>=1;i--){
        for(ll j=i+1;j<=i+c;j++){
            ans[j-i][min(j,to[i])]=S[i];
        }
    }
    ans[0]=S;
    for(ll i=1;i<=c;i++){
        for(ll j=1;j<=n;j++)if(ans[i][j]=='$') ans[i][j]=ans[i-1][j];
    }
    for(ll i=1;i<=n;i++)if(ans[c][i]!=T[i]) return cout<<"-1\n",void();
    cout<<c<<"\n";
    for(ll i=1;i<=c;i++) cout<<ans[i].substr(1,n)<<"\n";
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll Tc=1; cin>>Tc;
    for(;Tc--;){
        cin>>n>>k>>S>>T,S=" "+S,T=" "+T;
        solve();
    }
    return 0;
}

[CF2164D] Copy String 题解

文章操作

相关推荐

评论

[CF2164D] Copy String 题解