题解：P12727 [KOI 2021 Round 2] 公共括号子串字典序
sunkuangzheng
·
·
题解
注意 $S(A,B)$ 考虑的是本质不同子串，本质不同子串的字典序比较问题通常套路是按照 $sa_i$ 枚举后缀。将 $s+\texttt{\#}+t$ 后缀排序，考虑按照这个顺序枚举 $s$ 中字符串起点 $l$，则一个终点 $r$ 需要满足：
- $s[l,r]$ 在 $t$ 中出现了。
- $s[l,r]$ 没有在上一个前缀被统计到，即 $r-l+1 > \operatorname{lcp}(l,sa_{rk_l-1})$。
- $s[l,r]$ 是合法括号串，将左括号看作 $1$ 右括号看作 $-1$，这个条件又可以拆分成：
- $\forall i \in [l,r],\sum \limits_{j=l}^i s_j \ge 0$。
- $\sum \limits_{j=l}^r s_j = 0$。
不难发现这四个条件中，前三条都是有单调性的，我们逐一求出符合条件的边界 $r'$ 即可。
第一、二个条件即对于每个 $s$ 中后缀 $p$，寻找一个 $s$ 或 $t$ 中后缀 $q$ 使得 $\operatorname{lcp}(p,q)$ 最大。根据后缀数组相关理论，这个 $q$ 显然只可能是按 $rk$ 排好序后的前驱后继，按照 $rk$ 正反各自扫描一遍即可线性。
第三个条件等价于找到第一个 $pre_r < pre_{l-1}$ 的位置 $r$，单调栈即可线性。
第四个条件等价于数区间 $[l,r]$ 内 $x$ 的数量，注意到 $1 \le l \le r \le n,x \in [-n,n]$，离线差分桶排序即可线性。
因此总复杂度瓶颈在后缀排序的 $\mathcal O(n+m+|\Sigma|)$。
由于某些原因，下面的代码第四部分的实现带 $\log$。
```cpp
/**
* author: sunkuangzheng
* created: 21.06.2025 10:41:09
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
#include <algorithm>
#include <cassert>
#include <numeric>
#include <string>
#include <vector>
// namespace atcoder（限于篇幅以省略）
using ll = long long;
const int N = 1.2e6+5;
using namespace std;
int T,n,m,sa[N],rk[N],h[N],ok[N],l[N],pre[N],lim[N],st[N],tp;
string s,t; ll k; vector<int> pos[N];
void los(){
cin >> s >> t >> k,n = s.size();
for(int i = 0;i <= 2 * n;i ++) pos[i].clear();
for(int i = 1;i <= n;i ++){
pre[i] = pre[i - 1] + (s[i - 1] == '(' ? 1 : -1);
pos[pre[i] + n].push_back(i);
}s = s + '#' + t,m = s.size();
st[tp = 0] = n + 1;
for(int i = n;i >= 0;i --){
while(tp && pre[st[tp]] >= pre[i]) tp --;
lim[i] = st[tp],st[++tp] = i;
}auto _sa = atcoder::suffix_array(s); s = " " + s;
for(int i = 1;i <= m;i ++) rk[sa[i] = _sa[i-1] + 1] = i;
fill(ok,ok+m+1,0),fill(l,l+m+1,0),fill(h,h+m+1,0);
for(int i = 1,k = 0;i <= m;h[rk[i ++]] = k)
for(k = max(k-1,0);s[i + k] == s[sa[rk[i] - 1] + k];k ++);
for(int i = 1;i <= n;i ++) ok[rk[i]] = 1; ok[rk[n+1]] = -1;
int len = 0;
for(int i = 1;i <= m;len = min(len,h[++ i]))
if(ok[i] == 0) len = 1e9;
else if(ok[i] == 1) l[i] = max(l[i],len);
len = 0;
for(int i = m;i >= 1;len = min(len,h[i --]))
if(ok[i] == 0) len = h[i];
else if(ok[i] == 1) l[i] = max(l[i],len);
len = 0;
// for(int i = 1;i <= n;i ++) debug(rk[i],l[rk[i]]);
for(int i = 1;i <= m;len = min(len,h[++ i])) if(ok[i] == 1){
int p = sa[i];
int l = p + len,r = min(lim[p-1] - 1,p + ::l[i] - 1);
if(l > r) {len = 1e9; continue;}
auto &v = pos[pre[p-1] + n];
int cnt = upper_bound(v.begin(),v.end(),r) - lower_bound(v.begin(),v.end(),l);
if(k <= cnt){
int ql = lower_bound(v.begin(),v.end(),l) - v.begin();
int tr = v[ql + k - 1];
cout << s.substr(p,tr - p + 1) << "\n";
return ;
}else k -= cnt; len = 1e9;
}cout << "-1\n";
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(cin >> T;T --;) los();
}