QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#724290 | #5312. Levenshtein Distance | houbur | RE | 0ms | 0kb | C++14 | 1.8kb | 2024-11-08 11:42:31 | 2024-11-08 11:42:32 |
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