QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1080#684295#9522. A Simple String Problemmaspypengpeng_fudanSuccess!2024-10-28 15:17:022024-10-28 15:17:06

Details

Extra Test:

Wrong Answer
time: 0ms
memory: 3624kb

input:

2
aa
bb

output:

0

result:

wrong answer 1st lines differ - expected: '2', found: '0'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#684295#9522. A Simple String Problempengpeng_fudanWA 1515ms108004kbC++236.6kb2024-10-28 12:17:392024-10-28 15:18:57

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//不用桶排序
struct SuffixArray{
    vector<int> rk,sa;//sa[i]为排名第i的后缀起点,rk[i]为s[i,n-1]的排名
    vector<int> height;//height[i]为排名第i的和排名第i-1的字符串的最长公共前缀
    int n;
    //注意!!!全都是0~n-1的编码
    void intt(string& s){//m为筒的大小(比如小写字母为26),c为基准如'a'/'0'
        n=s.size();
        rk.resize(n),sa.resize(n);
        vector<int> cnt(n);
        height.resize(n+1);
        vector<pair<char,int>> res(n);
        for(int i=0;i<n;i++)    res[i]={s[i],i};
        sort(res.begin(),res.end());
        for(int i=0;i<n;i++) {sa[i]=res[i].second;}
        int q=0;
        for(int i=0;i<n;i++){
            if(i!=0&&res[i].first!=res[i-1].first)  q++;
            rk[res[i].second]=q;
        }
        for(int k=1;k<n;k<<=1){
            vector<int> tmp(n);
            int p=0;
            for(int i=n-k;i<=n-1;i++)   tmp[p++]=i;
            for(int i=0;i<n;i++){
                if(sa[i]>=k) tmp[p++]=sa[i]-k;  
            }   
            const int maxn=n;
            cnt.assign(maxn,0);
            for(int i=0;i<n;i++)    ++cnt[rk[tmp[i]]];
            for(int i=1;i<maxn;i++) cnt[i]+=cnt[i-1];
            for(int i=n-1;i>=0;i--){
                sa[--cnt[rk[tmp[i]]]]=tmp[i];
            }
            auto new_rk=[&](int x){
                return make_pair(rk[x],(x+k<=n-1?rk[x+k]:-1));
            };
            p=0;
            for(int i=0;i<n;i++){
                if(i==0)    tmp[sa[i]]=p;
                else    tmp[sa[i]]=(new_rk(sa[i-1])==new_rk(sa[i])?p:++p);
            } 
            rk=tmp;
            if(p==n)    break;
        }
        int pre=0;
        for(int i=0;i<n;i++){
            if(rk[i]==0)    continue;
            if(pre) pre--;
            int r=sa[rk[i]-1];
            while(r+pre<n&&i+pre<n&&s[r+pre]==s[i+pre]) pre++;
            height[rk[i]]=pre;
        }
    }
    vector<vector<int>> st;
    int maxn=0;
    void build_st(){
        maxn=0;
        while((1<<maxn)<=n) maxn++;
        st.resize(n);
        for(int i=0;i<n;i++){
            st[i].resize(maxn);
            st[i][0]=height[i];
        }
        for(int i=1;i<maxn;i++){
            for(int j=0;j<n;j++){
                if(j+(1<<i)<=n) st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);  
            }
        }     
    }
 	int lcp(int x,int y){//排名为x的后缀和排名为y的后缀的最长公共前缀
        assert(!st.empty());
        if(x>y) swap(x,y);
        if(x==y)    return n-sa[y];
        x++;
        int q=__lg(y-x+1);
        return min(st[x][q],st[y-(1<<q)+1][q]);
    }
     int lcp_rk(int x,int y){//排名为x的后缀和排名为y的后缀的最长公共前缀
        if(x>=n||x<0||y>=n||y<0)    return 0;
        if(x>y) swap(x,y);
        if(x==y)    return n-sa[y];
        x++;
        int q=__lg(y-x+1);
        return min(st[x][q],st[y-(1<<q)+1][q]);
    }
    int lcp_pz(int x,int y){
        if(x>=n||x<0||y>=n||y<0)    return 0;
        x=rk[x],y=rk[y];
        if(x>y) swap(x,y);
        if(x==y)    return n-sa[y];
        x++;
        int q=__lg(y-x+1);
        return min(st[x][q],st[y-(1<<q)+1][q]);
    }
    int get(int x,int len,int mo){
        if(mo==0){
            for(int i=maxn-1;i>=0;i--){
                if(x+(1<<i)-1<n&&st[x][i]>=len){
                    x+=(1<<i);
                }
            }
            return x;
        }
        else{
            for(int i=maxn-1;i>=0;i--){
                if(x-(1<<i)+1>=0&&st[x-(1<<i)+1][i]>=len){
                    x-=(1<<i);
                }
            }
            return x;
        }
    }
    pair<int,int> get_le_re(int x,int len){//和排名为x后缀最长公共前缀>=len的(l~r)排名
        return {get(x,len,1),get(x+1,len,0)-1};
    }
};
int get(string& s){
    SuffixArray lcp;lcp.intt(s);
    string w=s;reverse(w.begin(),w.end());
    SuffixArray lsp;lsp.intt(w);
    lcp.build_st();lsp.build_st();
    int sz=s.size();
    for(int i=sz/2;i>=1;i--){
        for(int lo=0,ro;lo<sz;lo=ro+1){
            ro=lo+i-1;if(ro>=sz)    break;
            if(lcp.lcp_pz(lo,ro+1)+lsp.lcp_pz(sz-ro-1,sz-lo)>=i)    return 2*i;
        }
    }
    return 0;
}
void solve(void) {
    int n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    int ans=0;
    auto ope=[&](int t)->void {
        for(int i=0;i<n;i++){
            if(a[i]==b[i])  ans=max(ans,2);
        }
        string a1=a,b1=b;
        string w1=a1+"#"+b1;
        reverse(a1.begin(),a1.end()),reverse(b1.begin(),b1.end());
        string w2=a1+"#"+b1;
        SuffixArray lcp;lcp.intt(w1);lcp.build_st();
        SuffixArray lsp;lsp.intt(w2);lsp.build_st();
        auto query_2lcp=[&](int x,int y)->int {
            return lcp.lcp_pz(x,y+n+1);
        };
        auto query_2lsp=[&](int x,int y)->int {
            return lsp.lcp_pz(n-x-1,2*n-y);
        };
        for(int i=(n+1)/2;i>=2;i--){
            for(int l1=0,r1;l1<n;l1=r1+1){
                r1=l1+i-1;if(r1>=n) break;
                int lo,ro;
                if(t==0){
                    lo=l1,ro=r1;
                }
                else{
                    lo=n-1-r1,ro=n-1-l1;
                }
                if(a[lo]==b[ro]){
                    int len1=min(query_2lsp(lo,ro),ro-lo+1);
                    int len2=min(query_2lcp(lo+1,ro+1),ro-lo);
                    if(len2+len1>=i)    {ans=max(ans,2*i);return ;}
                    int len3=-1;
                    int len4=min(lcp.lcp_pz(n+1+lo+len2,n+1+ro+1+len2),ro-(lo+len2));
                    if(len4)    len3=max(len3,len4+len2-1);
                    if(len3!=-1&&len3+len1>=i-1)      {ans=max(ans,2*i);return ;}
                }
                int len1=min(lcp.lcp_pz(n+lo+1,n+ro+2),ro-lo+1);
                int len2=min(lsp.lcp_pz(2*n-lo+1,2*n-ro),ro-lo+1);
                if(len2+len1>=i)    {ans=max(ans,2*i);return ;}
                int len3=len2;
                int len4=min(ro-lo+1-len2,query_2lsp(lo-len2,ro-len2));
                if(len4)    len3=max(len3,len4+len2);
                if(len3+len1>=i)  {ans=max(ans,2*i);return ;}

            }
        }




    };
    ope(0);
    swap(a,b);
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    ope(1);
    cout<<ans<<'\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _=1;
    while (_--) solve();

    return 0;
}
/*
10
abcdeabcde
bsbsbsbsad
*/
/*
3
abc
cab
*/
/*
20
abcdeabcdeabchhhhhhh
afafdasfsadfdeabcdef
*/