题解：P12729 [KOI 2021 Round 2] 最长公共括号子串

min_inf · 2025-06-07 21:41:51 · 题解

考虑二分，检查是否有 \ge len 的公共匹配串。

对于一个匹配串，设左括号为 1 右括号为 -1，那么所有后缀和为 0 的后缀都是匹配串，我们就截取最短的 \ge len 的后缀。这样我们只需要从两个串中分别拿出每个右端点往左最短的 \ge len 的合法后缀的哈希，检查是否有交即可。求这些串容易预处理一些数组做到线性。

ull pw[N];
struct str{
    string s;
    int n,lim;
    int a[N],p[N],nx[N],l[N];
    ull hs[N];
    void init(){
        cin>>s,n=s.size();
        a[0]=0;repn(i,n){
            a[i+1]=a[i]+(s[i]=='('?1:-1);
            hs[i+1]=hs[i]*131+s[i];
        }
        int mn=*min_element(a,a+n+1);
        rep(i,0,n)a[i]-=mn;
        lim=*max_element(a,a+n+1);
        rep(i,0,lim)p[i]=-1;per(i,n,0)nx[i]=p[a[i]],p[a[i]]=i;
        rep(i,0,lim)p[i]=-1;rep(i,0,n)l[i]=a[i]?p[a[i]-1]:-1,p[a[i]]=i;
    }
    ull gh(int l,int r){return hs[r]-hs[l]*pw[r-l];}
    vector<ull> get(int len){
        vector<ull> res;
        rep(i,0,lim)p[i]=-1;per(i,n,0)p[a[i]]=i;
        rep(i,1,n){
            while(nx[p[a[i]]]>=0&&i-nx[p[a[i]]]>=len)p[a[i]]=nx[p[a[i]]];
            if(p[a[i]]>l[i]&&i-p[a[i]]>=len)res.push_back(gh(p[a[i]],i));
        }
        return move(res);
    }
}a,b;

void solve(){
    a.init(),b.init();
    int l=0,r=min(a.s.size(),b.s.size());
    while(l<r){
        int mid=l+r+1>>1;
        vector<ull> A=a.get(mid),B=b.get(mid);
        sort(allc(A)),sort(allc(B));
        bool ok=0;
        auto it=B.begin();for(auto x:A){
            while(it!=B.end()&&*it<x)++it;
            if(it!=B.end()&&*it==x){ok=1;break;}
        }
        if(ok)l=mid;else r=mid-1;
    }
    cout<<l<<'\n';
}