P7081 题解

· · 题解

简要题意：给你串 A,B，你要进行一次操作 (S,T)，将 A 中出现的 S 替换成 T，如果有两个重叠的 S，那么只替换最左边的一个。

首先 S 和 T 分别是 A,B 的子串。观察到如果把 A 中出现的 S 标成特殊字符，B 中出现的 T 标成同样的字符，那么剩下的两个串必然相等。可以证明当 T\not =\empty 的时候这是充要条件。所以我们考虑如何计算 f_{l,r} 表示对 A 中的 S=A_{l,r} 依次替换成特殊字符后的哈希值。

我们枚举 [l,r] 的长度，先对每个 [l,r] 计算出开头在 r 后面的它第一次出现的地方 pos，这个可以从后往前扫一遍得到。然后令 g_{l,r} 表示对 A_{l,|A|} 中的 A_{l,r} 替换成特殊字符后的结果，这个是可以直接从 g_{pos,pos+r-l} 转移而来的。之后稍微处理一下就可以得到 f。同理我们对 B 也求一遍。如果有 l_1,r_1,l_2,r_2 使得 f_{A,l_1,r_1}=f_{B,l_2,r_2}，那么说明 S=A_{l1,r1},T=B_{l2,r2} 是一组合法的解。输出总长度最小的即可。

但我们仔细阅读题目，发现 T 可以是空串，所以需要求 h_{l,r} 表示把 A 中的 A_{[l,r]} 删掉而不是替换成特殊字符的哈希值，和 B 串的哈希值比较即可。

如果用 map 实现，时间复杂度 O(n^2\log n)。代码常数过大，洛谷上要跑 1.7s。

#define LJY main
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2005;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
const int TMP=rnd();
const int B=((rnd()>>11)<<7)|(rnd()&127)|3; // 随机 base，自然溢出
ull pw[N];string S,T;
struct Hsh{ // 哈希值
  int len;ull v;
  Hsh(){len=v=0;}
  Hsh(char x){len=1;v=x;}
  Hsh(int _l,ull _v):len(_l),v(_v){}
  bool operator<(const Hsh b)const{
    if(len!=b.len) return len<b.len;
    return v<b.v;
  }
}ss[N],st[N],fs[N][N],ft[N][N];
inline Hsh operator+(Hsh a,Hsh b){
  return {a.len+b.len,a.v*pw[b.len]+b.v};}
inline Hsh hsh1(int l,int r){
  if(l>r) return Hsh();
  return {r-l+1,ss[r].v-ss[l-1].v*pw[r-l+1]};}
inline Hsh hsh2(int l,int r){
  if(l>r) return Hsh();
  return {r-l+1,st[r].v-st[l-1].v*pw[r-l+1]};}
unordered_map<ull,int>mp;
map<Hsh,pair<int,int> >Mp;
void clear(unordered_map<ull,int>&x){
    unordered_map<ull,int>y;x.swap(y);}
signed LJY(){
  pw[0]=1;For(i,1,N-1) pw[i]=pw[i-1]*B;
  ios::sync_with_stdio(0);cin.tie(0);
  getline(cin,S);getline(cin,T);
  int n=S.size(),m=T.size();S=' '+S;T=' '+T;
  For(i,1,n) ss[i]=ss[i-1]+S[i];
  For(i,1,m) st[i]=st[i-1]+T[i];
  int ans=n+m;pair<int,int>U,V;
  U={1,n};V={1,m};

  For(len,1,n){
    For(l,1,n-len+1) fs[l][l+len-1]='*'+hsh1(l+len,n);
    clear(mp);
    ForDown(l,n-len+1,1){
      mp[hsh1(l,l+len-1).v]=l;Hsh tmp=hsh1(l-len,l-1);
      if(l-len>0&&mp.count(tmp.v)){
        int pos=mp[tmp.v]; // 用 unordered_map 找到下一个出现的位置，转移 g 
        fs[l-len][l-1]='*'+hsh1(l,pos-1)+fs[pos][pos+len-1]; 
      }
    }
    for(auto [_,x] within mp){ // 还留在 map 里的是可以成为最终哈希值的
            int r=x+len-1;
      fs[x][r]=hsh1(1,x-1)+fs[x][r]; // 加上一段前缀，计算出 f
      if(!Mp.count(fs[x][r])) Mp[fs[x][r]]={x,len}; // 放到 map 中便于后面查询
    }
  }
  For(len,1,m){
    For(l,1,m-len+1) ft[l][l+len-1]='*'+hsh2(l+len,m);
    clear(mp);
    ForDown(l,m-len+1,1){
      mp[hsh2(l,l+len-1).v]=l;Hsh tmp=hsh2(l-len,l-1);
      if(l-len>0&&mp.count(tmp.v)){
        int pos=mp[tmp.v];
        ft[l-len][l-1]='*'+hsh2(l,pos-1)+ft[pos][pos+len-1]; //同上
      }
    }for(auto [_,l] within mp){
            int r=l+len-1;
      ft[l][r]=hsh2(1,l-1)+ft[l][r]; // 同上
      if(Mp.count(ft[l][r])){
        auto [L,ln]=Mp[ft[l][r]];
        int res=ln+r-l+1; // 查询答案
        if(res<ans) ans=res,U={L,L+ln-1},V={l,r};
      }
    }
  }
  // -- T 非空的情况 ⬆
  // -- T 为空串的情况 ⬇
  For(len,1,n){
    For(l,1,n-len+1) fs[l][l+len-1]=hsh1(l+len,n);
    clear(mp);
    ForDown(l,n-len+1,1){
      mp[hsh1(l,l+len-1).v]=l;
      if(l-len>0&&mp.count(hsh1(l-len,l-1).v)){
        int pos=mp[hsh1(l-len,l-1).v];
        fs[l-len][l-1]=hsh1(l,pos-1)+fs[pos][pos+len-1]; // 不用加特殊字符
      }
    }
    for(auto [_,x] within mp){
            int r=x+len-1;
      fs[x][r]=hsh1(1,x-1)+fs[x][r];
      if(fs[x][r].len==m&&fs[x][r].v==st[m].v){ // 和 B 串比较
        if(ans>len) ans=len,U={x,r},V={1,0};
      }
    }
  }
  printf("s/");
  For(i,U.first,U.second) putchar(S[i]);putchar('/');
  For(i,V.first,V.second) putchar(T[i]);putchar('/');putchar('g');
  return 0;
}

不知道我是怎么把小清新题写成【数据删除】的。