自动搬运

查看原文

来自洛谷，原作者为

	stardust_Ray 无论前路如何，我都不会后悔与你的相遇

搬运于2025-08-24 22:26:29，当前版本为作者最后更新于2024-10-06 19:07:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意：给你串 $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;
}

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