|s_i|=|t_i|

cjdstttttt

2025-11-22 01:34:44

发布于：广东

14阅读

0回复

0点赞

如你所见，我代码调出来了。（喜）

定义可替换字符串如下：

对于 $A,B,S,T(|A|=|B|,|S|=|T|,A\not= B,S\not= T)$ ，

若存在至少一个 $[l,r]$ 使得 $[S_l,...,S_r]=A$ ，且将其中一个 $[S_l,...,S_r]$ 替换为 $B$ 后 $S=T$ ，

则成 $A,B$ 为 $S,T$ 的可替换字符串。

给定 $n$ 个字符串组合 $[A_1,B_1],[A_2,B_2],...,[A_n,B_n]$ ，其中 $|A_i|=|B_i|$ 。给出 $q$ 次询问，每次询问给出两个字符串 $S_i,T_i$ ，求出满足 $A_i,B_i$ 为 $S_i,T_i$ 的可替换字符串的 $i$ 的个数，特别地，若 $|S_i|\not= |T_i|$ ，输出 0。

$1\le n,q\le 2\times 10^5,1\le \sum |A_i|+|B_i|,\sum |S_i|+|T_i|\le 5\times 10^6$ 。即 $\sum A_i\le 2.5\times 10^6$ ，且对于所有答案不为 $0$ 的询问， $\sum S_i\le 2.5\times 10^6$ 。

首先考虑如何才能满足 $A,B$ 为 $S,T$ 的可替换字符串。

定义两个字符串 $S,T(|S|=|T|,S\not= T)$ 的核心为在所有满足除去该区间以外，所有的 $S_i=T_i$ 的区间中，长度最短的一个。

令 $[l,r]$ 为 $S,T$ 的核心， $[l',r']$ 为 $B$ 的核心， $A,B$ 为 $S,T$ 的可替换字符串当且仅当：

$[S_l,...,S_r]=[A_{l'},...,A_{r'}]$ 。
$[T_l,...,T_r]=[B_{l'},...,B_{r'}]$ 。
$[...,A_{l'}]$ 为 $[...,S_{l-1}]$ 的后缀。
$[A_{r+1},...]$ 为 $[S_{r+1},...]$ 的前缀。

知道这个结论后，就可以通过哈希 $O(nq)$ 求出了，搭配性质 B 可以得到 $70pts$ 的高分。

而且正解也很简单了……吗？

接下来才是真正折磨的点。

首先前面两个要求可以通过哈希快速寻找，后面的要求字典树很可做。

所以考虑 map 套 Trie 套 Trie。

map 第一个值是字符串的哈希值，第二个值是第一个 Trie 的根，可以用来快速查找满足前面两个条件的 $A_i,B_i$ 。

然后遍历 $[S_i,...,S_l]$ ，如果有这个节点，就再暴力进入第二个 Trie 找 $[S_r,...,S_j]$ ，将答案加上存在的个数。

例如：

5 1
abcdba abdcba
abcdbac abdcbac
bcdb bdcb
abcdbc abdcbc
a c
aabcdbabc aabdcbabc

构建 Trie 如下（黑节点表示 Trie 根，红节点表示前缀 Trie，绿节点表示后缀 Trie，标在绿节点上的黑字表示出现该字符串的个数）：

然后查询首先通过哈希找到根，然后按照建树相同的方法查询即可。蓝色的为遍历过程。

答案就为所有节点上的权值之和 $1+0+1=2$ 。

我们分析一下时间复杂度：

乍一看，很暴力，对于每个红节点都得搜一下叶子结点，最坏情况可能一次查询就要搜完整棵树。

但是——我们仔细分析一下建树过程。

注意到一个绿色节点就对应至少一个字符。

如果出题人想卡我们的话，肯定得像以下方法构造：

abaaaaaa... acaaaaaa...
aabaaaaaa... aacaaaaaa...
aaabaaaaaa... aaacaaaaaa...
...

造出来的这颗树大致长这样：

第一个 Trie 与第二个 Trie 深度均为 $O(\sqrt L)$ 。

而查询，如果要卡满，就需要把前后缀都拉满，字符串长度也得达到 $O(\sqrt L)$ 。

所以这时虽然单次查询复杂度为 $O(L)$ ，但总共也只会出现 $O(\sqrt L)$ 次查询，时间复杂度为 $O(L\sqrt L)$ 。

但这个复杂度要是实现得劣一点就寄了，所以我们还得减小时间复杂度。

注意到第二个 Trie 上的节点就对应了 $O(size)$ 个字符串，所以我们可以预处理出这些字符串的答案，然后查询时直接哈希二分找到对应的答案即可。

这样的话每次查询先 $O(|S_i|)$ 遍历第一个 Trie，然后 $O(\log^2 n)$ 二分判断第二个 Trie 包含的最长的前缀，时间复杂度就被我们优化到了 $O(L\log^2 L)$ 。

这时有人就要问了：这 $L=5\times 10^6$ ， $L\log^2 L\approx 2.5\times 10^9$ ，你这跟没优化有什么区别？

我们看看出题人最多能把我们卡成什么样。

首先看 $L$ 的定义： $\sum |S_i|+|T_i|$ 。所以我们得把 $L$ 除以 $2$ 计算。 $1.2\times 10^9$ 。

然后经过一番思考，发现最强的数据也就是按照上面的构造方法，将深度构造成 $O(\sqrt L)$ 。所以两个二分的大小其实都是 $O(\log \sqrt L)$ 的，又得乘一个 $\frac{1}{4}$ 。 $3\times 10^8$ 。而且你再怎么乱搞二分的常数都为 $1$ 吧。

这样，我们就通过了该题。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <memory.h>
#include <map>
#include <algorithm>
#define int unsigned long long
#define pii pair <int, int>
using namespace std;
const int mul = 131;
int ksm[2500005];
class String{
	vector <int> pre;
	int n;
	
	public:
	int size(){return n;}
	
	String(){
		n = 0;
		pre = {};
	}
	String(string s){
		s = ' ' + s;
		n = s.size() - 1;
		pre.resize(n + 5, 0);
		for(int i = 1; i <= n; i++){
			pre[i] = pre[i - 1] * mul + s[i];
		}
	}
	int substr(int left, int len){
		return (pre[left + len - 1] - pre[left - 1] * ksm[len]);
	}
};
int get_hash(string s){
	int ans = 0;
	for(char c:s){
		ans = ans * mul + c;
	}
	return ans;
}

class Trie2{
	public:
	
	char cur;
	int val;
	Trie2 *son[26];
	Trie2(){
		cur = val = 0;
		memset(son, 0, sizeof(son));
	}
};

class Trie1{
	public:
	
	char cur;
	Trie2 *next;
	Trie1 *son[26];
	vector <pii> mp;
	Trie1(){
		cur = 0;
		memset(son, 0, sizeof(son));
		mp.clear();
		next = new Trie2;
	}
};

void update(pii h, string s1, string s2, map <pii, Trie1*> &roots){
	if(!roots.count(h)) roots[h] = new Trie1;
	auto cur = roots[h];
	for(char c:s1){
		if(!cur -> son[c - 'a']) cur -> son[c - 'a'] = new Trie1;
		cur = cur -> son[c - 'a'];
		cur -> cur = c;
	}
	auto cur2 = cur -> next;
	for(char c:s2){
		if(!cur2 -> son[c - 'a']) cur2 -> son[c - 'a'] = new Trie2;
		cur2 = cur2 -> son[c - 'a'];
		cur2 -> cur = c;
	}
	cur2 -> val++;
}
void dfs(Trie2 *&cur, vector <pii> &v, int siz, int h){
	h = h * mul + cur -> cur;
	siz += cur -> val;
	v.push_back({h, siz});
	for(int i = 0; i < 26; i++){
		if(cur -> son[i]){
			dfs(cur -> son[i], v, siz, h);
		}
	}
	delete(cur);
}

void dfs2(Trie1 *cur){
	dfs(cur -> next, cur -> mp, 0, 0);
	sort(cur -> mp.begin(), cur -> mp.end());
	for(int i = 0; i < 26; i++){
		if(cur -> son[i]){
			dfs2(cur -> son[i]);
		}
	}
}

int query(Trie1 *cur, String s){
	int l = 0, r = s.size();
	while(l <= r){
		int mid = (l + r) >> 1;
		auto tmp = s.substr(1, mid);
		auto idx = lower_bound(cur -> mp.begin(), cur -> mp.end(), make_pair(tmp, 0ull));
		if(idx != cur -> mp.end() && idx -> first == tmp) l = mid + 1;
		else{
			if(r == 0) return 0;
			r = mid - 1;
		}
	}
	auto tmp = s.substr(1, r);
	return lower_bound(cur -> mp.begin(), cur -> mp.end(), make_pair(tmp, 0ull)) -> second;
}

string a[200005], b[200005];
map <pii, Trie1*> roots;
void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		if(a[i] == b[i]) continue;
		int l = 0, r = a[i].size() - 1;
		while(a[i][l] == b[i][l]) l++;
		while(a[i][r] == b[i][r]) r--;
		string s1 = a[i].substr(0, l), s2 = "";
		reverse(s1.begin(), s1.end());
		if(r < a[i].size() - 1) s2 = a[i].substr(r + 1, 350234350235ll);
		pii h = {get_hash(a[i].substr(l, r - l + 1)), 
				get_hash(b[i].substr(l, r - l + 1))};
		update(h, s1, s2, roots);
	}
	for(auto it:roots) dfs2(it.second);
	while(m--){
		string s, t;
		cin >> s >> t;
		if(s.size() != t.size()){
			cout << "0\n";
			continue;
		}
		int l = 0, r = s.size() - 1;
		while(s[l] == t[l]) l++;
		while(s[r] == t[r]) r--;
		string s1 = s.substr(0, l), s2 = "";
		reverse(s1.begin(), s1.end());
		if(r < s.size() - 1) s2 = s.substr(r + 1, 1145141919810ll);
		pii h = {get_hash(s.substr(l, r - l + 1)), 
				get_hash(t.substr(l, r - l + 1))};
		if(!roots.count(h)){
			cout << "0\n";
			continue;
		}
		auto cur = roots[h];
		String S(s2);
		int ans = query(cur, S);
		for(char c:s1){
			if(!cur -> son[c - 'a']) break;
			cur = cur -> son[c - 'a'];
			ans += query(cur, S);
		}
		std::cout << ans << '\n';
	}
	roots.clear();
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	ksm[0] = 1;
	for(int i = 1; i <= 2500000; i++){
		ksm[i] = ksm[i - 1] * mul;
	}
	int T = 1;
	while(T--) solve();

	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 3

cjdstttttt
ACGO数据最慢的点也是跑进829ms了

48分钟前来自广东
0
cjdstttttt
纪念第一次独立做出紫题！

49分钟前来自广东
0
cjdstttttt
d

9小时前来自广东
0

全部评论 3

热门讨论