QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#756232 | #9522. A Simple String Problem | Vegetable_Dog | AC ✓ | 1017ms | 6688kb | C++17 | 2.3kb | 2024-11-16 19:28:07 | 2024-11-16 19:28:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005;
int n;
char s[2][N];
const int bs=131;
const int mod=998244353;
int pw[N];
int hs[2][N];
int geths(int x,int l,int r){ return (hs[x][r]-1ll*hs[x][l-1]*pw[r-l+1]%mod+mod)%mod; }
void pre_work(){
pw[0]=1;
for(int i=1;i<N;i++)pw[i]=1ll*pw[i-1]*bs%mod;
for(int i=0;i<2;i++){
hs[i][0]=s[i][0];
for(int j=1;j<=n;j++)hs[i][j]=(1ll*hs[i][j-1]*bs+s[i][j])%mod;
}
}
int getlcp(int x1,int p1,int x2,int p2){
if(p1<0||p2<0||p1>n||p2>n)return 0;
int l=1,r=n-max(p1,p2)+1,mid,res=0;
while(l<=r){
mid=(l+r)>>1;
if(geths(x1,p1,p1+mid-1)==geths(x2,p2,p2+mid-1))res=mid,l=mid+1;
else r=mid-1;
}
return res;
}
int getlcs(int x1,int p1,int x2,int p2){
if(p1<0||p2<0||p1>n||p2>n)return 0;
int l=1,r=min(p1,p2)+1,mid,res=0;
while(l<=r){
mid=(l+r)>>1;
if(geths(x1,p1-mid+1,p1)==geths(x2,p2-mid+1,p2))res=mid,l=mid+1;
else r=mid-1;
}
return res;
}
int ans=0;
int work1(){
int res=0;
for(int d=1;d*2<=n+1;d++){
bool flag=0;
for(int i=0;i+d<=n;i+=d){
if(s[1][i]!=s[1][i+d])continue;
int rm1=i+d+getlcp(1,i,1,i+d)-1;
int lm1=i-getlcs(1,i,1,i+d)+1;
int lm0=lm1-getlcs(0,lm1-1,1,lm1+d-1);
if(rm1-lm0+1>=d*2){
flag=1;
break;
}
}
if(flag)res=max(res,d*2);
}
return res;
}
int work2(){
int res=0;
for(int d=1;d*2<=n+1;d++){
bool flag=0;
for(int i=0;i+d<=n;i+=d){
if(s[0][i]!=s[1][i+d])continue;
int lm=getlcs(0,i,1,i+d);
int rm=getlcp(0,i,1,i+d);
if(lm+rm-1>=d){
flag=1;
break;
}
int t1=getlcs(0,i-lm,0,i+d-lm);
int t2=getlcp(1,i+rm,1,i+d+rm);
if(lm+rm-1+max(t1,t2)>=d){
flag=1;
break;
}
}
if(flag)res=max(res,d*2);
}
return res;
}
int work3(){
int res=0;
for(int d=1;d*2<=n+1;d++){
bool flag=0;
for(int i=0;i+d<=n;i+=d){
if(s[0][i]!=s[0][i+d])continue;
int lm0=i-getlcs(0,i,0,i+d)+1;
int rm0=i+d+getlcp(0,i,0,i+d)-1;
int rm1=rm0+getlcp(1,rm0+1,0,rm0-d+1);
if(rm1-lm0+1>=d*2){
flag=1;
break;
}
}
if(flag)res=max(res,d*2);
}
return res;
}
int main(){
scanf("%d",&n);
scanf("%s%s",s[0],s[1]+1);
s[0][n]='$'; s[1][0]='#';
pre_work();
ans=max(ans,work1());
ans=max(ans,work2());
ans=max(ans,work3());
printf("%d",ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4736kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5996kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 6028kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4604kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 99ms
memory: 6600kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 99ms
memory: 6460kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 95ms
memory: 6540kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 811ms
memory: 6528kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1017ms
memory: 6540kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 956ms
memory: 6688kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 96ms
memory: 6460kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5844kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 1ms
memory: 4600kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 1ms
memory: 4604kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 1ms
memory: 4744kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 1ms
memory: 4484kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4664kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 1ms
memory: 4676kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 1ms
memory: 4668kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed