「SWTR-05」E String

Alex_Wei · 2020-03-17 14:19:18 · 题解

题面传送门。

题意简述：给定两个字符串 s,t。每次可以切除 t 的一个前/后缀并保证其为切割后的 t 的子串。求得到 s 的最少操作数或给出无解。

题目可以理解为：每次操作将 s 的一个子串拼在其前/后。求得到 t 的最少操作数。

一些约定：

设 m=|s|,n=|t|。设区间 [l,r] 为 t 的第 l 位至第 r 位字符组成的字符串。

• 如何判断无解：如果 s 没有在 t 中出现，或者 t 出现了 s 没有的字母，即无解。可以 O(n^2) 暴力判断，也可以 O(n) KMP 求解。std 使用 O(n^2) 暴力判断。

Subtask 1：s=t。

输出 0 即可。

Subtask 2：s 仅包含小写字母 \texttt{a}。

先判断是否无解，否则答案为最小的满足 m\times 2^c\geq n 成立的整数 c。

Subtask 3：n\leq 100。

区间 DP。设 f_{i,j} 为 s 扩展到区间 [l,r] 的最少步数。转移时枚举粘贴字符串的长度，暴力匹配。枚举 l,r:O(n^2)，转移枚举长度 :O(n)，暴力匹配 :O(n)。时间复杂度 O(n^4)，常数极小。

Subtask 4：n\leq 500。

将暴力匹配改成字符串哈希即可做到 O(1) 匹配。总时间复杂度 O(n^3)，常数较小。

如果实现精细 + 极小常数，O(n^4) 也许可以暴力艹过去。

Subtask 5：n\leq 1.5\times 10^3。

验题人 @chenxia25 给出的算法时间复杂度为 n^2\log n。这里放上他的原话（有删减）：

“如果已经算出了 f_{l,r}，考虑它能影响哪些更大的区间的 f 值。显然只能从两端扩展。”

“以往左为例，能扩展到 l'（能影响 f_{l',r}）当且仅当 [l',l-1] 是 [l,r] 的子串。那么所有 l' 显然构成区间。”

“用 z 算法算出 t 中两两点的 LCS，区间 RMQ 即可得到最小的 l'，然后线段树区间更新维护。”

“还有一个小小的优化方法可以把它弄成 BIT。”

这里给出他的代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int lowbit(int x){return x&-x;}
const int N=1500,M=1500;
int n,m;
char a[N+5],b[M+5];
int cov[N+1][M+1];
int lcP[N+1][M+1],Lcs[M+1][M+1];
int s;
char c[N+M+6];
void con(char s1[],int p1,int l1,char s2[],int p2,int l2){
    s=0;
    for(int i=p1;i<=l1;i++)c[++s]=s1[i];
    c[++s]='!';
    for(int i=p2;i<=l2;i++)c[++s]=s2[i];
}
int z[N+M+2];
void z_init(){
    z[1]=s;
    int zl=0,zr=0;
    for(int i=2;i<=s;i++)
        if(zr<i){
            z[i]=0;
            while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
            if(z[i])zl=i,zr=i+z[i]-1;
        }
        else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];
        else{
            z[i]=zr-i+1;
            while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
            zl=i;zr=i+z[i]-1;
        }
}
struct bitree{
    int val[M+2],mn[M+1];
    void init(){memset(val,0x3f,sizeof(val));memset(mn,0x3f,sizeof(mn));}
    void chkmn(int x,int v){
        if(v>=val[x])return;
        val[x]=v;
        while(x<=m)mn[x]=min(mn[x],v),x+=lowbit(x);
    }
    int Mn(int x){
        int res=inf;
        while(x)res=min(res,mn[x]),x-=lowbit(x);
        return res;
    }
}bit[M+1],bitr[M+1];
int lft[M+1][M+1],rit[M+1][M+1];
int dp[M+1][M+1];
int main(){
    cin>>b+1>>a+1;
    n=strlen(a+1);m=strlen(b+1);
    con(a,1,n,b,1,m);z_init();
    for(int i=1;i<=m;i++)if(z[n+1+i]==n)cov[i][i+n-1]=true;
    for(int i=1;i<=m;i++){
        con(b,i,m,b,1,m);z_init();
        for(int j=1;j<=m;j++)lcP[i][j]=z[m-i+1+1+j];
    }
    reverse(b+1,b+m+1);
    for(int i=1;i<=m;i++){
        con(b,i,m,b,1,m);z_init();
        for(int j=1;j<=m;j++)Lcs[m-i+1][m-j+1]=z[m-i+1+1+j];
    }
    for(int i=1;i<=m;i++)bit[i].init(),bitr[i].init();
    for(int i=m;i;i--)for(int j=i;j<=m;j++){
        dp[i][j]=cov[i][j]?0:min(bit[j].Mn(i),bitr[i].Mn(m-j+1));
        bit[j].chkmn(i-(lft[i][j]=max(lft[i][j-1],min(Lcs[j][i-1],j-i+1))),dp[i][j]+1);
        bitr[i].chkmn(m-(j+(rit[i][j]=max(rit[i+1][j],min(lcP[i][j+1],j-i+1))))+1,dp[i][j]+1);
    }
    cout<<(dp[1][m]==inf?-1:dp[1][m]);
    return 0;
}

Subtask 6：|s|=4，数据随机。

留给乱搞。

Subtask 7：n\leq 5\times 10^3。

不妨换个思路，设 f_{l,r} 为区间 [l,r] 往左边（即头部）能粘贴的子串长度最大值，g_{l,r} 为区间 [l,r] 往右边（即尾部）能粘贴的子串长度最大值。

如果求出了 f 和 g，我们可以通过一遍 BFS 求出答案。BFS 具体实现方法见代码，这里不再赘述。

• 如何预处理 f,g？

  回忆一下 f,g 的定义：区间 [l,r] 往左/右能粘贴的子串长度最大值。如果认真思考，就能发现 f_{l,r} 一定不小于 f_{l,r-1}(l<r)，因为区间 [l,r-1] 能往左粘贴的子串，区间 [l,r] 也一定能做到，其长度就具有单调性。g 同理。合理运用单调性和字符串哈希，就能在 O(n^2) 的时间内计算 f,g。

预处理 f,g 时间复杂度 O(n^2)，BFS 时间复杂度 O(n^2)。时间复杂度 O(n^2)。

• 应评论区补充一点：不难发现每次扩展的长度越大越好。感性理解一下，类似上面 f_{l,r} 一样，区间 [l,r] 能够扩展的长度一定不小于 [l+1,r] 或 [l,r-1]。

• 另外也可以直接 DP 求答案，按照区间长度从小到大扩展即可。

#include<bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define int short
#define pii pair <int,int>
#define fi first
#define se second

const int N=5e3+5;
const int bs=131;

ull hs[N],pw[N];
ull cal(int l,int r){return hs[r]-hs[l-1]*pw[r-l+1];}

string s,t;
int f[N][N],g[N][N],dp[N][N],n;
queue <pii> q;

signed main(){
    cin>>t>>s,n=t.size(); if(s==t)puts("0"),exit(0);

    pw[0]=1; for(int i=1;i<=n;i++)pw[i]=pw[i-1]*bs;
    for(int i=0;i<n;i++)hs[i+1]=hs[i]*bs+(t[i]-'a');

    for(int i=1;i<=n;i++){
        int tmp=1;
        for(int j=i;j<=n;j++){
            while(tmp<i&&j-tmp+1>=i&&cal(i-tmp,i-1)==cal(j-tmp+1,j))tmp++;
            f[i][j]=tmp-1;
        } tmp=1;
        for(int j=i;j;j--){
            while(i+tmp<=n&&j+tmp-1<=i&&cal(j,j+tmp-1)==cal(i+1,i+tmp))tmp++;
            g[j][i]=tmp-1;
        }
    }

    int pos=t.find(s); if(pos==-1)puts("-1"),exit(0);
    while(pos!=-1)q.push({pos+1,pos+s.size()}),pos=t.find(s,pos+1);
    while(!q.empty()){
        int l=q.front().fi,r=q.front().se,dl=f[l][r],dr=g[l][r],d=dp[l][r]; q.pop(); 
        if(dl!=0){l-=dl; if(!dp[l][r])dp[l][r]=d+1,q.push({l,r}); l+=dl;}
        if(dr!=0){r+=dr; if(!dp[l][r])dp[l][r]=d+1,q.push({l,r}); r-=dr;}
    }
    cout<<(dp[1][n]?dp[1][n]:-1)<<endl; 
    return 0;
}