QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#686663 | #9522. A Simple String Problem | Tx_Lcy | AC ✓ | 1182ms | 8600kb | C++14 | 2.1kb | 2024-10-29 15:02:54 | 2024-11-10 22:37:30 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-29 15:02:54]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=2e5+10;
int const B=251;
mt19937_64 rnd(random_device{}());
ull rd[127],hsh1[N],hsh2[N],bse[N];int ans,n;
string s1,s2;
inline ull query1(int l,int r){return hsh1[r]-hsh1[l-1]*bse[r-l+1];}
inline ull query2(int l,int r){return hsh2[r]-hsh2[l-1]*bse[r-l+1];}
#define mid ((l+r)>>1)
inline int lcp1(int x,int y){
int l=1,r=min(n-x+1,n-y+1),ans=0;
while (l<=r)
if (query1(x,x+mid-1)==query1(y,y+mid-1)) l=(ans=mid)+1;
else r=mid-1;
return ans;
}
inline int lcs1(int x,int y){
int l=1,r=min(x,y),ans=0;
while (l<=r)
if (query1(x-mid+1,x)==query1(y-mid+1,y)) l=(ans=mid)+1;
else r=mid-1;
return ans;
}
inline int lcp(int x,int y){
int l=1,r=min(n-x+1,n-y+1),ans=0;
while (l<=r)
if (query1(x,x+mid-1)==query2(y,y+mid-1)) l=(ans=mid)+1;
else r=mid-1;
return ans;
}
inline void work(){
rep(len,1,(n+1)/2){
if (2*len<=ans) continue;
for (int i=1;i+len<=n;i+=len){
int A=i,B=i+len;
if (lcp(A,B-1)>=len){ans=max(ans,len*2);break;}
int sa=lcs1(A,B),sb=lcp1(A,B);
if (sa+sb-1>=len){ans=max(ans,len*2);break;}
else{
int k=lcp(A+sb,B+sb-1);
if (k+sa+sb-1>=len){ans=max(ans,len*2);break;}
}
{
int sa=lcp1(A+1,B+1);
if (sa>=len){ans=max(ans,len*2);break;}
if (lcp(A+sa+1,B+sa)+sa>=len){ans=max(ans,len*2);break;}
}
}
}
}
inline void solve(){
cin>>n>>s1>>s2,s1=" "+s1,s2=" "+s2;
if (n==1){
if (s1[1]==s2[1]) cout<<"2\n";
else cout<<"0\n";
return;
}
rep(i,'a','z') rd[i]=rnd();
rep(i,1,n)
hsh1[i]=(hsh1[i-1]*B+rd[s1[i]]),
hsh2[i]=(hsh2[i-1]*B+rd[s2[i]]);
work();
swap(s1,s2);
for (int i=1;i<n-i+1;++i) swap(s1[i],s1[n-i+1]),swap(s2[i],s2[n-i+1]);
rep(i,1,n)
hsh1[i]=(hsh1[i-1]*B+rd[s1[i]]),
hsh2[i]=(hsh2[i-1]*B+rd[s2[i]]);
work();
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
bse[0]=1;
rep(i,1,N-1) bse[i]=bse[i-1]*B;
int t=1;
while (t--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5848kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 6764kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5840kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5160kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 6560kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 6688kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 982ms
memory: 8444kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 482ms
memory: 8468kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 964ms
memory: 8508kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 1182ms
memory: 8428kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 521ms
memory: 8600kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 504ms
memory: 8436kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 979ms
memory: 8476kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 1ms
memory: 8304kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 1ms
memory: 6720kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5740kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 1ms
memory: 7136kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 1ms
memory: 6828kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 1ms
memory: 6960kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 1ms
memory: 6396kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed