专栏文章

题解：P14363 [CSP-S 2025] 谐音替换 / replace（民间数据）

hhrdgy
P14363题解参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mineiigj
此快照首次捕获于
2025/12/02 01:06
3 个月前
此快照最后确认于
2025/12/02 01:06
3 个月前
查看原文

Trie+Hash 简单线性做法

考虑将每个替换抽象成一个四元组 (Ls,Xs,Ys,Rs)(L_s,X_s,Y_s,R_s) ：
其中 XsX_s 与 YsY_s 为 si,1s_{i,1} 与 si,2s_{i,2} 极长不同的子串 ， LsL_s 为极长相同的前缀 ， RsR_s 为极长相同的后缀 。
对于每一个询问 tt 我们也可以类似地定义四元组 (Lt,Xt,Yt,Rt)(L_t,X_t,Y_t,R_t) 。
我们很容易发现一个合法的替换满足如下四个条件：
  1. LsL_s 是 LtL_t 的后缀
  2. RsR_s 是 RtR_t 的前缀
  3. Xs=XtX_s=X_t
  4. Ys=YtY_s=Y_t
考虑继续转换为三个限制条件：
  1. Ls+XsL_s+X_s 是 Lt+XtL_t+X_t 长度大于等于 ∣Xs∣\left| X_s \right| 的后缀
  2. Ys+RsY_s+R_s 是 Yt+RtY_t+R_t 长度大于等于 ∣Xs∣\left| X_s \right| 的前缀
  3. ∣Xs∣=∣Xt∣\left| X_s \right| = \left| X_t \right|
正确性可以证明
其中后缀限制进行翻转后可以变为前缀限制
  • 第一个限制可以看成是字典树上的一条路径
  • 第二个限制挂在字典树结点上，查询时在路径上查询
  • 第三个限制挂在字典树结点上，查询时在路径上查询
对于第二个限制，我们用 Ys+RsY_s+R_s 的哈希值表示这个串。
对于第三个限制，我们把每个长度随机赋权，并把长度对应权值乘进 Ys+RsY_s+R_s 的哈希值后挂在树上。
这样我们的每一次查询的流程如下：
  1. 先找出 Lt+XtL_t+X_t 长度大于等于 ∣Xs∣\left| X_s \right| 的后缀在字典树上对应的路径
  2. 枚举 Yt+RtY_t+R_t 长度大于等于 ∣Xs∣\left| X_s \right| 的前缀，在树上路径查询。
如果在线做可以用主席树做到 O(Llog⁡n)O(L\log n)
如果离线下来，让每个字典树的节点找到他可以贡献的询问一起做，复杂度就是线性的。
1.4K代码
CPP
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define left wshnl
#define right wkqnl
using namespace std;
const int N=200005;
const int M=5e6+5; 
mt19937_64 rnd(time(0));
int n,q,ans[N];ull w[M];
int ch[M][30],trie=1;
ull base=131;
vector<ull>add[M];
struct event{
	int u,op;ull tm;
};
vector<event>e[M];
unordered_map<ull,int>cnt;
void dfs(int u){
	for(auto i:add[u])cnt[i]++;
	for(auto i:e[u])ans[i.u]+=i.op*cnt[i.tm];
	for(int i=0;i<26;i++)if(ch[u][i])dfs(ch[u][i]);
	for(auto i:add[u])cnt[i]--;
}
int main(){
	for(int i=1;i<M;i++)w[i]=rnd();
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		string x,y;cin>>x>>y;
		int l,r;
		for(l=0;l<x.size()&&x[l]==y[l];l++);
		for(r=x.size()-1;r>=0&&x[r]==y[r];r--);
		int u,k;
		for(u=1,k=r;k>=0;u=ch[u][x[k]-'a'],k--){
			if(!ch[u][x[k]-'a'])ch[u][x[k]-'a']=++trie;
		}
		ull H=0;
		for(int j=l;j<x.size();j++)H=H*base+y[j];
		H*=w[r-l+1];
		add[u].push_back(H);
	}
	for(int i=1;i<=q;i++){
		string x,y;cin>>x>>y;
		if(x.size()!=y.size())continue;
		int l,r;
		for(l=0;l<x.size()&&x[l]==y[l];l++);
		for(r=x.size()-1;r>=0&&x[r]==y[r];r--);
		int u,v=1,k;
		for(u=1,k=r;k>=0&&ch[u][x[k]-'a'];u=ch[u][x[k]-'a'],k--)if(k>=l)v=u;
		if(k>=l)continue;
		ull H=0;int ans=0;
		for(int j=l;j<x.size();j++){
			H=H*base+y[j];
			if(j<r)continue;
			e[u].push_back((event){i,1,H*w[r-l+1]});
			e[v].push_back((event){i,-1,H*w[r-l+1]});
		}	
	}
	dfs(1);
	for(int i=1;i<=q;i++)cout<<ans[i]<<"\n";
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...