自动搬运

查看原文

来自洛谷，原作者为

	sunkuangzheng **

搬运于2025-08-24 23:17:45，当前版本为作者最后更新于2025-06-21 11:47:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$\mathcal O(n+m+|\Sigma|)$ 的线性做法！！111，虽然字符集大小只有 $2$。

注意 $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$。

/**
 *    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();
}