QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#684295 | #9522. A Simple String Problem | pengpeng_fudan | WA | 1513ms | 108056kb | C++23 | 6.6kb | 2024-10-28 12:17:39 | 2024-10-28 14:31:22 |
Judging History
你现在查看的是测评时间为 2024-10-28 14:31:22 的历史记录
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-28 15:17:17]
- hack成功,自动添加数据
- (/hack/1080)
- [2024-10-28 14:28:57]
- hack成功,自动添加数据
- (/hack/1079)
- [2024-10-28 12:17:39]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//不用桶排序
struct SuffixArray{
vector<int> rk,sa;//sa[i]为排名第i的后缀起点,rk[i]为s[i,n-1]的排名
vector<int> height;//height[i]为排名第i的和排名第i-1的字符串的最长公共前缀
int n;
//注意!!!全都是0~n-1的编码
void intt(string& s){//m为筒的大小(比如小写字母为26),c为基准如'a'/'0'
n=s.size();
rk.resize(n),sa.resize(n);
vector<int> cnt(n);
height.resize(n+1);
vector<pair<char,int>> res(n);
for(int i=0;i<n;i++) res[i]={s[i],i};
sort(res.begin(),res.end());
for(int i=0;i<n;i++) {sa[i]=res[i].second;}
int q=0;
for(int i=0;i<n;i++){
if(i!=0&&res[i].first!=res[i-1].first) q++;
rk[res[i].second]=q;
}
for(int k=1;k<n;k<<=1){
vector<int> tmp(n);
int p=0;
for(int i=n-k;i<=n-1;i++) tmp[p++]=i;
for(int i=0;i<n;i++){
if(sa[i]>=k) tmp[p++]=sa[i]-k;
}
const int maxn=n;
cnt.assign(maxn,0);
for(int i=0;i<n;i++) ++cnt[rk[tmp[i]]];
for(int i=1;i<maxn;i++) cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;i--){
sa[--cnt[rk[tmp[i]]]]=tmp[i];
}
auto new_rk=[&](int x){
return make_pair(rk[x],(x+k<=n-1?rk[x+k]:-1));
};
p=0;
for(int i=0;i<n;i++){
if(i==0) tmp[sa[i]]=p;
else tmp[sa[i]]=(new_rk(sa[i-1])==new_rk(sa[i])?p:++p);
}
rk=tmp;
if(p==n) break;
}
int pre=0;
for(int i=0;i<n;i++){
if(rk[i]==0) continue;
if(pre) pre--;
int r=sa[rk[i]-1];
while(r+pre<n&&i+pre<n&&s[r+pre]==s[i+pre]) pre++;
height[rk[i]]=pre;
}
}
vector<vector<int>> st;
int maxn=0;
void build_st(){
maxn=0;
while((1<<maxn)<=n) maxn++;
st.resize(n);
for(int i=0;i<n;i++){
st[i].resize(maxn);
st[i][0]=height[i];
}
for(int i=1;i<maxn;i++){
for(int j=0;j<n;j++){
if(j+(1<<i)<=n) st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
int lcp(int x,int y){//排名为x的后缀和排名为y的后缀的最长公共前缀
assert(!st.empty());
if(x>y) swap(x,y);
if(x==y) return n-sa[y];
x++;
int q=__lg(y-x+1);
return min(st[x][q],st[y-(1<<q)+1][q]);
}
int lcp_rk(int x,int y){//排名为x的后缀和排名为y的后缀的最长公共前缀
if(x>=n||x<0||y>=n||y<0) return 0;
if(x>y) swap(x,y);
if(x==y) return n-sa[y];
x++;
int q=__lg(y-x+1);
return min(st[x][q],st[y-(1<<q)+1][q]);
}
int lcp_pz(int x,int y){
if(x>=n||x<0||y>=n||y<0) return 0;
x=rk[x],y=rk[y];
if(x>y) swap(x,y);
if(x==y) return n-sa[y];
x++;
int q=__lg(y-x+1);
return min(st[x][q],st[y-(1<<q)+1][q]);
}
int get(int x,int len,int mo){
if(mo==0){
for(int i=maxn-1;i>=0;i--){
if(x+(1<<i)-1<n&&st[x][i]>=len){
x+=(1<<i);
}
}
return x;
}
else{
for(int i=maxn-1;i>=0;i--){
if(x-(1<<i)+1>=0&&st[x-(1<<i)+1][i]>=len){
x-=(1<<i);
}
}
return x;
}
}
pair<int,int> get_le_re(int x,int len){//和排名为x后缀最长公共前缀>=len的(l~r)排名
return {get(x,len,1),get(x+1,len,0)-1};
}
};
int get(string& s){
SuffixArray lcp;lcp.intt(s);
string w=s;reverse(w.begin(),w.end());
SuffixArray lsp;lsp.intt(w);
lcp.build_st();lsp.build_st();
int sz=s.size();
for(int i=sz/2;i>=1;i--){
for(int lo=0,ro;lo<sz;lo=ro+1){
ro=lo+i-1;if(ro>=sz) break;
if(lcp.lcp_pz(lo,ro+1)+lsp.lcp_pz(sz-ro-1,sz-lo)>=i) return 2*i;
}
}
return 0;
}
void solve(void) {
int n;
cin>>n;
string a,b;
cin>>a>>b;
int ans=0;
auto ope=[&](int t)->void {
for(int i=0;i<n;i++){
if(a[i]==b[i]) ans=max(ans,2);
}
string a1=a,b1=b;
string w1=a1+"#"+b1;
reverse(a1.begin(),a1.end()),reverse(b1.begin(),b1.end());
string w2=a1+"#"+b1;
SuffixArray lcp;lcp.intt(w1);lcp.build_st();
SuffixArray lsp;lsp.intt(w2);lsp.build_st();
auto query_2lcp=[&](int x,int y)->int {
return lcp.lcp_pz(x,y+n+1);
};
auto query_2lsp=[&](int x,int y)->int {
return lsp.lcp_pz(n-x-1,2*n-y);
};
for(int i=(n+1)/2;i>=2;i--){
for(int l1=0,r1;l1<n;l1=r1+1){
r1=l1+i-1;if(r1>=n) break;
int lo,ro;
if(t==0){
lo=l1,ro=r1;
}
else{
lo=n-1-r1,ro=n-1-l1;
}
if(a[lo]==b[ro]){
int len1=min(query_2lsp(lo,ro),ro-lo+1);
int len2=min(query_2lcp(lo+1,ro+1),ro-lo);
if(len2+len1>=i) {ans=max(ans,2*i);return ;}
int len3=-1;
int len4=min(lcp.lcp_pz(n+1+lo+len2,n+1+ro+1+len2),ro-(lo+len2));
if(len4) len3=max(len3,len4+len2-1);
if(len3!=-1&&len3+len1>=i-1) {ans=max(ans,2*i);return ;}
}
int len1=min(lcp.lcp_pz(n+lo+1,n+ro+2),ro-lo+1);
int len2=min(lsp.lcp_pz(2*n-lo+1,2*n-ro),ro-lo+1);
if(len2+len1>=i) {ans=max(ans,2*i);return ;}
int len3=len2;
int len4=min(ro-lo+1-len2,query_2lsp(lo-len2,ro-len2));
if(len4) len3=max(len3,len4+len2);
if(len3+len1>=i) {ans=max(ans,2*i);return ;}
}
}
};
ope(0);
swap(a,b);
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
ope(1);
cout<<ans<<'\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _=1;
while (_--) solve();
return 0;
}
/*
10
abcdeabcde
bsbsbsbsad
*/
/*
3
abc
cab
*/
/*
20
abcdeabcdeabchhhhhhh
afafdasfsadfdeabcdef
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 1249ms
memory: 107980kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 1235ms
memory: 107972kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 1222ms
memory: 107780kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 1426ms
memory: 108056kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 696ms
memory: 107992kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 735ms
memory: 107988kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 1513ms
memory: 107860kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed