QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1080 | #684295 | #9522. A Simple String Problem | maspy | pengpeng_fudan | Success! | 2024-10-28 15:17:02 | 2024-10-28 15:17:06 |
详细
Extra Test:
Wrong Answer
time: 0ms
memory: 3624kb
input:
2 aa bb
output:
0
result:
wrong answer 1st lines differ - expected: '2', found: '0'
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#684295 | #9522. A Simple String Problem | pengpeng_fudan | WA | 1515ms | 108004kb | C++23 | 6.6kb | 2024-10-28 12:17:39 | 2024-10-28 15:18:57 |
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
*/