QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722734 | #9522. A Simple String Problem | grass8cow | AC ✓ | 1456ms | 104852kb | C++17 | 2.2kb | 2024-11-07 20:04:46 | 2024-11-10 22:38:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int sa[N],t[N],tr[N],rk[N],m,h[N],st[N][20];
char c[N];
int lg[N];
int lcp(int x,int y){
x=rk[x],y=rk[y];if(x>y)swap(x,y);x++;
int k=lg[y-x+1];
return min(st[x][k],st[y-(1<<k)+1][k]);
}
void SA(int n){
lg[0]=-1;
for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
m=128;
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++)t[rk[i]=c[i]]++;
for(int i=1;i<=m;i++)t[i]+=t[i-1];
for(int i=n;i;i--)sa[t[rk[i]]--]=i;
for(int k=1;;k<<=1){
int o=0;
for(int i=n-k+1;i<=n;i++)tr[++o]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)tr[++o]=sa[i]-k;
for(int i=1;i<=m;i++)t[i]=0;
for(int i=1;i<=n;i++)t[rk[i]]++;
for(int i=1;i<=m;i++)t[i]+=t[i-1];
for(int i=n;i;i--)sa[t[rk[tr[i]]]--]=tr[i];
swap(tr,rk),rk[sa[1]]=o=1;
for(int i=2;i<=n;i++)
rk[sa[i]]=(tr[sa[i-1]]==tr[sa[i]]&&tr[sa[i-1]+k]==tr[sa[i]+k])?o:(++o);
if(o==n)break;m=o;
}
for(int i=1,k=0;i<=n;i++){
if(k)k--;int j=sa[rk[i]-1];
while(c[i+k]==c[j+k]&&i+k<=n&&j+k<=n)k++;
st[rk[i]][0]=k;
}
for(int j=1;j<20;j++)for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int n;
int Lcp(bool f1,bool f2,bool f3,int x,int y){
if(f1)x=n+1-x,y=n+1-y;
if(x>n||y>n)return 0;
if(!f1)return min(min(n-x+1,n-y+1),lcp(x+(f2?(n*2):0),y+(f3?(n*2):0)));
return min(min(n-x+1,n-y+1),lcp(x+n+(f2?(n*2):0),y+n+(f3?(n*2):0)));
}
char a[200100],b[200100];
//把a正反串和b拼进来跑sa
int mx;
void Sol(){
int L=0;
for(int i=1;i<=n;i++)c[++L]=a[i];c[++L]='1';
c[++L]='2';for(int i=n;i;i--)c[++L]=a[i];
c[++L]='3';for(int i=1;i<=n;i++)c[++L]=b[i];
for(int i=n;i;i--)c[++L]=b[i];c[++L]='4';
SA(L);n++;
for(int k=1;k<=n;k++){
bool gg=0;
for(int i=0;i+k<=n;i+=k){
int l1=Lcp(0,0,0,i+1,i+k+1),l2=Lcp(1,0,0,i,i+k);
if(l1+l2>=k||Lcp(0,0,1,i+1+l1,i+k+1+l1)>=k-l1-l2)gg=1;
l1=Lcp(0,0,1,i+1,i+k+1),l2=Lcp(1,0,1,i,i+k);
if(l1+l2>=k||Lcp(1,0,0,i-l2,i+k-l2)>=k-l1-l2)gg=1;
}
if(gg)mx=max(mx,k);
}
n--;
}
int main(){
scanf("%d%s%s",&n,a+1,b+1);
Sol();
reverse(a+1,a+n+1),reverse(b+1,b+n+1);
for(int i=1;i<=n;i++)swap(a[i],b[i]);
Sol();
printf("%d\n",mx*2);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 32584kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 4ms
memory: 34676kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 3ms
memory: 32520kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 8ms
memory: 32484kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 3ms
memory: 36660kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 6ms
memory: 34632kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 1445ms
memory: 104420kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 1452ms
memory: 101636kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 1456ms
memory: 102048kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 1229ms
memory: 103096kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1143ms
memory: 104852kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 1454ms
memory: 102384kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 1111ms
memory: 102000kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 8ms
memory: 32480kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 8ms
memory: 32628kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 8ms
memory: 34612kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 7ms
memory: 32448kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 8ms
memory: 34544kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 4ms
memory: 32508kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 7ms
memory: 32632kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 7ms
memory: 34636kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed