QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#725433 | #9522. A Simple String Problem | qvzeyang | AC ✓ | 702ms | 87428kb | C++23 | 3.7kb | 2024-11-08 17:45:10 | 2024-11-08 17:45:10 |
Judging History
你现在查看的是测评时间为 2024-11-08 17:45:10 的历史记录
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-08 17:45:10]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pr pair<int,int>
#define _(x,y) x=(x+y)%mod
#define ll long long
int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}
#define N 800105
#define M 800110
int cnt[M],id[M],rk[M],ork[M],sa[M],height[M],ans,st[M][20],len;
char s[M],S[N],T[N];
inline void suffixArray(){
int n=len;
int m=300,p=0;
for(int i=1;i<=n;++i) cnt[rk[i]=s[i]]++;
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
for(int w=1;p^n;w<<=1,m=p){
memset(cnt,0,sizeof(cnt)),p=0;
for(int i=n;i>n-w;--i) id[++p]=i;
for(int i=1;i<=n;++i) if(sa[i]>w) id[++p]=sa[i]-w;
for(int i=1;i<=n;++i) cnt[rk[i]]++;
for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i) sa[cnt[rk[id[i]]]--]=id[i];
memcpy(ork,rk,sizeof(ork)),p=0;
for(int i=1;i<=n;++i)
rk[sa[i]]=(ork[sa[i]]==ork[sa[i-1]]&&ork[sa[i]+w]==ork[sa[i-1]+w])?p:++p;
}
}
inline void getHeight(){
int n=len;
for(int i=1,k=0;i<=n;++i){
if(k) k--;
while(s[i+k]==s[sa[rk[i]-1]+k]) k++;
height[rk[i]]=k;
}
}
int n;
inline int queryMin(int x,int y){
if(x>y) swap(x,y);
int k=__lg(y-x+1);
return min(st[x][k],st[y-(1<<k)+1][k]);
}
inline int querySS(int x,int y){
x=rk[x],y=rk[y];
if(x>y) swap(x,y);
return queryMin(x+1,y);
}
inline int queryTT(int x,int y){
x=rk[x+2*n+2],y=rk[y+2*n+2];
if(x>y) swap(x,y);
return queryMin(x+1,y);
}
inline int queryST(int x,int y){
x=rk[x],y=rk[y+2*n+2];
if(x>y) swap(x,y);
return queryMin(x+1,y);
}
inline int querySSR(int x,int y){
x=rk[n+1+n-x+1],y=rk[n+1+n-y+1];
if(x>y) swap(x,y);
return queryMin(x+1,y);
}
inline int queryTTR(int x,int y){
x=rk[3*n+3+n-x+1],y=rk[3*n+3+n-y+1];
if(x>y) swap(x,y);
return queryMin(x+1,y);
}
inline int querySTR(int x,int y){
x=rk[n+1+n-x+1],y=rk[3*n+3+n-y+1];
if(x>y) swap(x,y);
return queryMin(x+1,y);
}
inline void work(){
memset(cnt,0,sizeof(cnt));
memset(id,0,sizeof(id));
memset(rk,0,sizeof(rk));
memset(ork,0,sizeof(ork));
memset(sa,0,sizeof(sa));
memset(height,0,sizeof(height));
for(int i=1;i<=n;++i){
s[i]=S[i];
s[i+n+1]=S[n-i+1];
s[i+2*n+2]=T[i];
s[i+3*n+3]=T[n-i+1];
}
s[n+1]='*';
s[2*n+2]='#';
s[3*n+3]='@';
len=4*n+3;
suffixArray(),getHeight();
for(int i=1;i<=len;++i) st[i][0]=height[i];
for(int j=1;j<20;++j){
for(int i=1;i+(1<<j)-1<=len;++i){
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
for(int l=n;l>=1;--l){
for(int i=l;i+l<=n;i+=l){
int j=i+l;
if(T[i]==T[j]){
int R=queryTT(i,j)-1;
int L=queryTTR(i,j)-1;
int tmp=L+R+querySTR(i-L-1,j-L-1);
if(tmp>=j-i-1){
ans=max(ans,l);
return;
}
}
if(S[i]==T[j]){
int L=querySTR(i,j)-1;
int R=queryST(i,j)-1;
int tmp=L+R+queryTT(i+R+1,j+R+1);
if(tmp>=j-i-1){
ans=max(ans,l);
return;
}
}
}
}
}
signed main(){
n=read();
scanf("%s%s",S+1,T+2);
n++;
S[n]='.';
T[1]=',';
work();
reverse(S+1,S+n+1);
reverse(T+1,T+n+1);
swap(S,T);
work();
cout<<ans*2;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 27976kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 4ms
memory: 27840kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 28012kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 27844kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 4ms
memory: 25976kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 3ms
memory: 27820kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 652ms
memory: 87364kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 604ms
memory: 87212kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 617ms
memory: 87404kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 702ms
memory: 87344kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 474ms
memory: 87420kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 502ms
memory: 87428kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 319ms
memory: 87404kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 3ms
memory: 27880kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 6ms
memory: 27824kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 4ms
memory: 25984kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 4ms
memory: 25980kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 27620kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 27968kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 4ms
memory: 25916kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 3ms
memory: 27568kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed