QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#763318 | #5312. Levenshtein Distance | harlem | TL | 1ms | 3692kb | C++11 | 2.7kb | 2024-11-19 19:32:28 | 2024-11-19 19:32:28 |
Judging History
answer
//调了一下午,最后只能找思路相近的代码调试,所以和别人代码会相似TAT
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define dprint(x) cout<<#x<<"="<<x<<"\n"
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ull bas=13331;
const int K=35,N=1e5+5;
int k;
string s,t;
int ss,ts;
int f[K][K*2];
#define g(i,j) f[i][j+k]
ull shsh[N],thsh[N];
int ned[N],ans[N];
inline ull qpow(ull a,ull b){
ull res=1;
while(b){
if(b&1)res*=a;
a*=a;
b>>=1;
}
return res;
}
void hashinit(){
for(int i=1;i<=ss;i++){
shsh[i]=shsh[i-1]*bas+s[i-1];
}
for(int i=1;i<=ts;i++){
thsh[i]=thsh[i-1]*bas+t[i-1];
}
}
bool check(int sa,int sb,int ta,int tb){
return shsh[sb]-shsh[sa-1]*qpow(bas,sb-sa+1)==thsh[tb]-thsh[ta-1]*qpow(bas,tb-ta+1);
}
int sa(int sa,int sb,int ta,int tb){
if(sa>sb||ta>tb)return 0;
int l=0,r=min(sb-sa+1,tb-ta+1);
while(l<r){
int m=l+r+1>>1;
if(check(sa,sa+m-1,ta,ta+m-1))l=m;
else r=m-1;
}
return l;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>k>>s>>t;
ss=s.size();ts=t.size();
hashinit();
for(int be=0;be<ts;be++){
memset(f,-1,sizeof(f));
g(0,0)=0;
for(int i=0;i<=k;i++){
for(int j=-i;j<=i;j++){
if(g(i,j)!=-1){
g(i,j)+=sa(g(i,j)+1,ss,be+g(i,j)+j+1,ts);
if(i<k){
chmax(g(i+1,j),g(i,j)+1);
chmax(g(i+1,j+1),g(i,j));
chmax(g(i+1,j-1),g(i,j)+1);
}
}
}
}
int l=max(be+1,be+ss-k),r=min(ts,be+ss+k);
if(l>r)continue;
for(int i=l;i<=r;i++)ned[i]=k+1;
for(int i=0;i<=k;i++){
for(int j=-i;j<=i;j++){
if(g(i,j)>=ss)chmin(ned[min(ts,be+ss+j)],i);
}
}
for(int i=l;i<=r;i++){
ans[ned[i]]++;
}
}
for(int i=0;i<=k;i++)cout<<ans[i]<<"\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3692kb
input:
4 aaa aabbaab
output:
0 5 15 7 1
result:
ok 5 number(s): "0 5 15 7 1"
Test #2:
score: -100
Time Limit Exceeded
input:
30 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...