QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#724290#5312. Levenshtein DistancehouburRE 0ms0kbC++141.8kb2024-11-08 11:42:312024-11-08 11:42:32

Judging History

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

  • [2024-11-08 11:42:32]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-08 11:42:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
const int N=5e4+5,bs=237;
int n,m,k;
int x,y,z,l,r,ans[N];
string s,t;
int f[35][101];
//f[i][j]表示编辑距离小于等于i,匹配上的字符串|s|-|t|=j,最大能延伸到的位置为f[i][j]
//因为j<=k,所以状态数最多只会有k^2个转移直接效仿求编辑距离的转移就好
ull hss[N],hst[N],a[N];
inline ull get_hashs(int l,int r){return hss[r]-hss[l-1]*a[r-l+1];}
inline ull get_hasht(int l,int r){return hst[r]-hst[l-1]*a[r-l+1];}
inline bool check(int x,int y,int len){return get_hashs(x,x+len-1)==get_hasht(y,y+len-1);}
inline int LCP(int x,int y){
	int l=1,r=min(n-x+1,m-y+1),res=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(x,y,mid))l=mid+1,res=mid;
		else r=mid-1;
	}return res;
}
signed main(){
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>k;
	cin>>s>>t;
	n=s.size();m=t.size();
	s=' '+s;t=' '+t;a[0]=1;
	for(int i=1;i<=max(n,m);i++)a[i]=a[i-1]*bs;
	for(int i=1;i<=n;i++)hss[i]=hss[i-1]*bs+s[i];
	for(int i=1;i<=m;i++)hst[i]=hst[i-1]*bs+t[i];
	for(int st=1;st<=m;st++){
		for(int i=0;i<=k;i++)for(int j=-i;j<=i;j++)f[i][j+k]=0;
		f[0][k]=0;
		for(int i=0;i<=k;i++){
			for(int j=-i;j<=i;j++){
				f[i][j+k]+=LCP(f[i][j+k]+1,st+f[i][j+k]+j);
				if(i!=k){
					f[i+1][j+k-1]=max(f[i+1][j+k-1],min(n,f[i][j+k]+1));
					f[i+1][j+k]=max(f[i+1][j+k],min(f[i][j+k]+1,n));
					f[i+1][j+k+1]=max(f[i+1][j+k+1],f[i][j+k]);
				}
			}
		}
		for(int j=-k;j<=k;j++){
			if(j+n<=0||j+n>m-st+1)continue;
			for(int i=0;i<=k;i++){
				if(f[i][j+k]==n){ans[i]++;break;}
			}
		}
	}	
	for(int i=0;i<=k;i++)cout<<ans[i]<<"\n";
	return 0;
}

詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

4
aaa
aabbaab

output:


result: