QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#732747 | #9522. A Simple String Problem | sz051 | AC ✓ | 501ms | 11392kb | C++20 | 2.2kb | 2024-11-10 15:44:56 | 2024-11-10 22:38:56 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int md=998244353,bas=131;
void read(int &x){
x=0;
char c=getchar();
while(!('0'<=c && c<='9')){
c=getchar();
}
while('0'<=c && c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
}
int n,pw[600010],hsh[600010];
char s[600010];
int gethsh(int l,int r){
if(l>r){
return 0;
}
return (hsh[r]+(md-pw[r-l+1])*hsh[l-1])%md;
}
int getlcp(int i,int j,int upl){
//printf("[LCP %lld %lld %lld]:",i,j,upl);
int ql=0,qr=upl+1;
while(ql<qr-1){
int mid=(ql+qr)>>1;
if(gethsh(i,i+mid-1)==gethsh(j,j+mid-1)){
ql=mid;
}else{
qr=mid;
}
}
//printf("[%lld]\n",ql);
return ql;
}
int getlcs(int i,int j,int upl){
//printf("[LCS %lld %lld %lld]:",i,j,upl);
int ql=0,qr=upl+1;
while(ql<qr-1){
int mid=(ql+qr)>>1;
if(gethsh(i-mid+1,i)==gethsh(j-mid+1,j)){
ql=mid;
}else{
qr=mid;
}
}
//printf("[%lld]\n",ql);
return ql;
}
signed main(){
pw[0]=1;
for(int i=1;i<=400005;i++){
pw[i]=pw[i-1]*bas%md;
}
read(n);
n++;
scanf(" %s %s",s+1,s+n+2);
s[n+1]='#';
for(int i=1;i<=2*n;i++){
hsh[i]=(hsh[i-1]*bas+s[i])%md;
}
//printf("[%lld %lld]",gethsh(1,3),gethsh(10,12));
int res=0;
for(int i=1;i<=n/2;i++){
for(int j=i;j+i<=n;j+=i){
int cl=getlcs(j,j+i,i),cr=getlcp(j+1,j+i+1,min(i-cl,n-j-i));
if(j+2*i-cl>n){
continue;
}
if(cl+cr==i || gethsh(j+cr+1,j+i-cl)==gethsh(n+j+cr+1+i,n+j+i+i-cl)){
res=i;
break;
}
}
if(res==i){
continue;
}
for(int j=i;j+i<=n;j+=i){
int cl=getlcs(n+j,n+j+i,i),cr=getlcp(n+j+1,n+j+i+1,min(i-cl,n-j-i));
if(cl+cr==i || gethsh(j+cr-i+1,j-cl)==gethsh(n+j+cr+1,n+j+i-cl)){
res=i;
break;
}
}
if(res==i){
continue;
}
for(int j=i;j+i<=n;j+=i){
int cl=getlcs(j,n+j+i,i),cr=getlcp(j+1,n+j+i+1,min(i-cl,n-j-i));
if(cl+cr==i || gethsh(j+cr-i+1,j-cl)==gethsh(j+cr+1,j+i-cl)){
res=i;
break;
}
if(j+2*i-cl<=n && gethsh(n+j+cr+1,n+j+i-cl)==gethsh(n+j+cr+1+i,n+j+i+i-cl)){
continue;
}
}
}
printf("%lld",res*2);
return 0;
}
/*
5
abcab
acabc
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5580kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5744kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 2ms
memory: 5580kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 5692kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5572kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 7628kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 435ms
memory: 10132kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 434ms
memory: 11392kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 440ms
memory: 9780kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 489ms
memory: 10484kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 477ms
memory: 9788kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 501ms
memory: 11164kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 434ms
memory: 10836kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 3ms
memory: 7784kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 2ms
memory: 6024kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 5652kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 2ms
memory: 5780kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 3ms
memory: 7792kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 2ms
memory: 5584kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 2ms
memory: 5928kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 2ms
memory: 5696kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed