QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#763318#5312. Levenshtein DistanceharlemTL 1ms3692kbC++112.7kb2024-11-19 19:32:282024-11-19 19:32:28

Judging History

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

  • [2024-11-19 19:32:28]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3692kb
  • [2024-11-19 19:32:28]
  • 提交

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

output:


result: