QOJ.ac

QOJ

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

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-28 15:18:57]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:WA
  • 用时:1515ms
  • 内存:108004kb
  • [2024-10-28 15:17:17]
  • hack成功,自动添加数据
  • (/hack/1080)
  • [2024-10-28 14:31:22]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1513ms
  • 内存:108056kb
  • [2024-10-28 14:28:57]
  • hack成功,自动添加数据
  • (/hack/1079)
  • [2024-10-28 12:17:39]
  • 评测
  • 测评结果:100
  • 用时:1532ms
  • 内存:108104kb
  • [2024-10-28 12:17:39]
  • 提交

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
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3828kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 1242ms
memory: 107856kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 1208ms
memory: 107908kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 1236ms
memory: 107904kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 1408ms
memory: 108004kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 707ms
memory: 107932kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 738ms
memory: 107848kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 1515ms
memory: 107976kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3832kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: -3
Extra Test Failed : Wrong Answer on 6
time: 0ms
memory: 3652kb

input:

2
aa
bb

output:

0

result:

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