QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723299 | #5312. Levenshtein Distance | Ishar-zdl | WA | 0ms | 3656kb | C++14 | 2.0kb | 2024-11-07 21:45:10 | 2024-11-07 21:45:11 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10,mod=998244353,inf=1e9,P=17771;
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
int K,n,m,f[35][70],ans[N];
ull hs[2][N],p[N];
char s[N],t[N];
inline int get(int l,int r,int id){return hs[id][r]-hs[id][l-1]*p[r-l+1];}
inline int LCP(int x,int y){
if(x<0||x>n||y<0||y>m)return 0;
int l=1,r=std::min(n-x+1,m-y+1),res=0;
while(l<=r){
int mid=l+r>>1;
if(get(x,x+mid-1,0)==get(y,y+mid-1,1))l=mid+1,res=mid;
else r=mid-1;
}return res;
}
signed main(){
// freopen("edit.in","r",stdin);freopen("edit.out","w",stdout);
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
std::cin>>K>>s+1>>t+1;n=strlen(s+1),m=strlen(t+1);
p[0]=1;for(int i=1;i<=std::max(n,m);++i)p[i]=p[i-1]*P;
for(int i=1;i<=n;++i)hs[0][i]=hs[0][i-1]*P+s[i]-'a'+1;
for(int i=1;i<=m;++i)hs[1][i]=hs[1][i-1]*P+t[i]-'a'+1;
for(int st=1;st<=m;++st){
for(int i=0;i<=K;++i)for(int j=0;j<=2*K;++j)f[i][j]=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,f[i][j+K]+st+j);
if(i!=K)
Max(f[i+1][j+K-1],std::min(f[i][j+K]+1,n)),
Max(f[i+1][j+K],std::min(f[i][j+K]+1,n)),
Max(f[i+1][j+K+1],f[i][j+K]);
}
for(int j=std::max(-K,1-n);j<=std::min(K,m-st-n+1);++j)
for(int i=0;i<=K;++i)if(f[i][j+K]>=n){ans[i]++;break;}
}ll sum=0;for(int i=0;i<=K;++i)sum+=ans[i];
std::cout<<sum<<'\n';
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3656kb
input:
4 aaa aabbaab
output:
28
result:
wrong answer 1st numbers differ - expected: '0', found: '28'