QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#403777#5312. Levenshtein DistanceqwqUwU_RE 493ms12952kbC++172.4kb2024-05-02 18:49:452024-05-02 18:49:45

Judging History

你现在查看的是最新测评结果

  • [2024-05-02 18:49:45]
  • 评测
  • 测评结果:RE
  • 用时:493ms
  • 内存:12952kb
  • [2024-05-02 18:49:45]
  • 提交

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...

output:


result: