|s_i|=|t_i|
2025-11-22 01:34:44
发布于：广东
如你所见，我代码调出来了。（喜）
定义可替换字符串如下：
对于 ，
若存在至少一个 使得 ，且将其中一个 替换为 后 ，
则成 为 的可替换字符串。
给定 个字符串组合 ，其中 。给出 次询问，每次询问给出两个字符串 ，求出满足 为 的可替换字符串的 的个数，特别地，若 ，输出 0。
。即 ，且对于所有答案不为 的询问，。
首先考虑如何才能满足 为 的可替换字符串。
定义两个字符串 的核心为在所有满足除去该区间以外，所有的 的区间中，长度最短的一个。
令 为 的核心， 为 的核心， 为 的可替换字符串当且仅当：
- 。
- 。
- 为 的后缀。
- 为 的前缀。
知道这个结论后，就可以通过哈希 求出了，搭配性质 B 可以得到 的高分。
而且正解也很简单了……吗？
接下来才是真正折磨的点。
首先前面两个要求可以通过哈希快速寻找，后面的要求字典树很可做。
所以考虑 map 套 Trie 套 Trie。
map 第一个值是字符串的哈希值，第二个值是第一个 Trie 的根，可以用来快速查找满足前面两个条件的 。
然后遍历 ，如果有这个节点，就再暴力进入第二个 Trie 找 ，将答案加上存在的个数。
例如：
5 1
abcdba abdcba
abcdbac abdcbac
bcdb bdcb
abcdbc abdcbc
a c
aabcdbabc aabdcbabc
构建 Trie 如下（黑节点表示 Trie 根，红节点表示前缀 Trie，绿节点表示后缀 Trie，标在绿节点上的黑字表示出现该字符串的个数）：
然后查询首先通过哈希找到根，然后按照建树相同的方法查询即可。蓝色的为遍历过程。
答案就为所有节点上的权值之和 。
我们分析一下时间复杂度：
乍一看，很暴力，对于每个红节点都得搜一下叶子结点，最坏情况可能一次查询就要搜完整棵树。
但是——我们仔细分析一下建树过程。
注意到一个绿色节点就对应至少一个字符。
如果出题人想卡我们的话，肯定得像以下方法构造：
abaaaaaa... acaaaaaa...
aabaaaaaa... aacaaaaaa...
aaabaaaaaa... aaacaaaaaa...
...
造出来的这颗树大致长这样：
第一个 Trie 与第二个 Trie 深度均为 。
而查询，如果要卡满，就需要把前后缀都拉满，字符串长度也得达到 。
所以这时虽然单次查询复杂度为 ，但总共也只会出现 次查询，时间复杂度为 。
但这个复杂度要是实现得劣一点就寄了，所以我们还得减小时间复杂度。
注意到第二个 Trie 上的节点就对应了 个字符串，所以我们可以预处理出这些字符串的答案，然后查询时直接哈希二分找到对应的答案即可。
这样的话每次查询先 遍历第一个 Trie，然后 二分判断第二个 Trie 包含的最长的前缀，时间复杂度就被我们优化到了 。
这时有人就要问了：这 ，，你这跟没优化有什么区别？
我们看看出题人最多能把我们卡成什么样。
首先看 的定义：。所以我们得把 除以 计算。。
然后经过一番思考，发现最强的数据也就是按照上面的构造方法，将深度构造成 。所以两个二分的大小其实都是 的，又得乘一个 。。而且你再怎么乱搞二分的常数都为 吧。
这样，我们就通过了该题。
#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;
}
有帮助，赞一个