QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#403777 | #5312. Levenshtein Distance | qwqUwU_ | RE | 493ms | 12952kb | C++17 | 2.4kb | 2024-05-02 18:49:45 | 2024-05-02 18:49:45 |
Judging History
answer
// clang-format off
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef pair<ll,ll> pll; typedef pair<int,ll> pil;
inline ll read(){
ll x=0,f=1,c=getchar();
while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=1e5+3;
// clang-format on
int n,m,K;
char S[N],T[N];
int A[N<<1];
int sa[N<<1],rk[N<<1],st[18][N<<1];
inline int lcp(int i,int j){
if(i>n||j>m)return 0;
i=rk[i],j=rk[j+n+1];
if(i>j)swap(i,j);
int k=__lg(j-i++);
return min(st[k][i],st[k][j-(1<<k)+1]);
}
int f[35][65];
inline void ckmax(int &x,int y){x=max(x,y);}
inline int& F(int i,int j){return f[i][j+K];}
int main() {
//freopen("data.in", "r", stdin);
// freopen(".in","r",stdin);
//freopen("myans.out","w",stdout);
K=read();scanf("%s",S+1),n=strlen(S+1);
scanf("%s",T+1);m=strlen(T+1);
rep(i,1,n)A[i]=S[i];A[n+1]=32;
rep(i,1,m)A[n+1+i]=T[i];
static int cnt[N<<1];int len=n+m+1,lim=127;
rep(i,1,len)++cnt[rk[i]=A[i]];
rep(i,1,lim)cnt[i] += cnt[i-1];
per(i,len,1)sa[cnt[rk[i]]--]=i;
for(int w=1,p=0;w<=len;w<<=1,lim=p,p=0){
static int id[N<<1];
per(i,len,len-w+1)id[++p]=i;
rep(i,1,len)if(sa[i]>w)id[++p]=sa[i]-w;
memset(cnt,0,sizeof cnt);
rep(i,1,len)++cnt[rk[id[i]]];
rep(i,1,lim)cnt[i] += cnt[i-1];
per(i,len,1)sa[cnt[rk[id[i]]]--]=id[i],id[i]=0;
static int tmp[N<<1];swap(tmp,rk);
p=0;rep(i,1,len)rk[sa[i]]=(tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+w]==tmp[sa[i-1]+w]?p:++p);
if(p==n)break;
}
rep(i,1,len){
if(rk[i]==1)continue;
int &k=st[0][rk[i]]=max(0,st[0][rk[i-1]]-1);
while(A[i+k]==A[sa[rk[i]-1]+k])++k;
}
rep(j,1,17)rep(i,1,len-(1<<j)+1)st[j][i]=min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
static int ans[32];
rep(ST,0,m-1){
memset(f,-1,sizeof f);F(0,0)=0;
rep(i,0,K)rep(j,-i,i)if(~F(i,j)){
F(i,j) += lcp(F(i,j)+1,F(i,j)+ST+j+1);
if(i==K)continue;
ckmax(F(i+1,j+1),F(i,j));
ckmax(F(i+1,j),F(i,j)+1);
ckmax(F(i+1,j-1),F(i,j)+1);
}
rep(j,-min(K,n-1),min(K,m-n-ST))rep(i,abs(j),K)if(F(i,j)>=n){ ++ans[i];break;}
}
rep(i,0,K)printf("%d\n",ans[i]);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6200kb
input:
4 aaa aabbaab
output:
0 5 15 7 1
result:
ok 5 number(s): "0 5 15 7 1"
Test #2:
score: 0
Accepted
time: 354ms
memory: 12752kb
input:
30 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 31 numbers
Test #3:
score: 0
Accepted
time: 323ms
memory: 12904kb
input:
30 BBAAABAABBBA ABBABBBBAABAAAABABBBAABAABBAABAAAAAABAABABBAAAABAAAAABABAABAABBABBAAAABBBBAABBABAAABAABAABBBBBABBABABBBBABBBBAAABBABABBBBAAABBBBAAAABABABABABABABAAABBBBBAABAABAABBAABBBAABBBBBBBABAABAABAABABAABAAABAABBBAABABBABBAAABAAAABABABBABBBAAABBBAAAABBBBABABABAABAABBBBBBBBBAABBBABABBBABAABBABBA...
output:
17 662 8230 50302 166666 310121 345469 280387 227200 209178 203013 198561 105117 102147 99771 97730 96058 94730 93633 92720 92060 91525 91143 90831 90585 90419 90288 90200 90120 90068 90035
result:
ok 31 numbers
Test #4:
score: 0
Accepted
time: 493ms
memory: 12868kb
input:
30 AAABBAAAAAAAAAAAAABAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAABAAAAABAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABABAAAABAAAABAAAABAAAAABAAAAAABAAAAAAAAABAAABAAABBAAAAAAAAAAAAAAAABAABAAABAAAAAAAAAAAAABAAAAAAAAAAAAAAAABAAABBAAAAAAAAAAAAAAAAAAAAAAAAAABAABAABABAAAAAAAAAAAAAAA...
output:
0 0 0 0 1 28 263 1410 6434 22523 56017 115080 189633 263874 316906 339254 332825 312943 286470 263283 246310 235032 227182 221294 216978 213734 211178 208848 206945 205393 204279
result:
ok 31 numbers
Test #5:
score: 0
Accepted
time: 326ms
memory: 12852kb
input:
30 ABABAABAAABAAAA AABBABABBBBBAAABABAABBAAABBBAABABBBABABABABABBABBBAAAAABBAAABBABABABABABBAAABBAAABAAABBBBBBBAABABBBAAAAABAABBBABBABBBABBBABABAABABBBAAABBABBAAABBBBBBBAABAABABAAAAAABBAABAAABBBAABBAABBAABBABABAAAAAAAABBBBBAAABABABBABAAAAABAABAABAABAABAAABABBABBBABAAABBBABABAABAABBBAABABBAABBAAAABAB...
output:
2 125 1938 15793 70756 178090 282937 325020 310617 277899 244094 217672 206966 202456 198644 105535 102767 100355 98411 96655 95310 94124 93217 92487 91872 91414 91039 90741 90555 90397 90276
result:
ok 31 numbers
Test #6:
score: 0
Accepted
time: 414ms
memory: 12952kb
input:
30 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
0 0 0 0 1 91 1082 14598 58877 123681 212928 258264 253856 277926 265254 243456 217809 198008 190004 184665 184470 183593 183524 183406 183335 183255 183185 183142 183078 182991 182922
result:
ok 31 numbers
Test #7:
score: -100
Runtime Error
input:
30 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAABABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...