前置知识
解法
考虑分别计算出编辑距离恰好等于 \(k_{0} \in [0,k]\) 的答案。
观察在编辑距离的存在下，长度差至多为 \(k\)。
考虑设 \(f_{i,j}\) 表示最大的 \(x\) 使得 \(s_{1 \sim x}\) 和 \(t_{1 \sim x+j}\) 可以在 \(i\) 次编辑内得到，即从 \(1\) 开始操作 \(i\) 次且长度增加 \(j\) 的最大匹配位置。
- 显然 \(x,i\) 具有单调性。
转移时考虑截取一段 \(t\) 的后缀进行转移。
假设已经操作完了，那么 \(f_{i,j}\) 能向外延伸的就是 \(s_{f_{i,j}+1,|s|}\) 和 \(t_{f_{i,j}+j+1,|t|}\) 的公共前缀，查询 \(\operatorname{LCP}\) 进行更新即可。
\(\operatorname{LCP}\) 可以用二分哈希单次 \(O(\log n)\) 查询，也可以后缀数组 \(O(n \log n)\) 预处理完 \(O(1)\) 查询。
转移时考虑刷表，分别对 \(f_{i+1,j-1},f_{i+1,j},f_{i+1,j+1}\) 进行转移（三者分别对应删除、替换、添加）。
- 注意下标为负数时的移位。
统计贡献时在遇到第一个合法的 \(i\) 加入贡献即可。
如果用后缀数组的话时间复杂度为 \(O(nk^{2}+n \log n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
int f[15][25],ans[15];
char s[100010],t[100010],tmp[100010];
struct SA
{
struct ST
{
int fminn[100010][25];
void init(int n,int a[])
{
memset(fminn,0x3f,sizeof(fminn));
for(int i=1;i<=n;i++)
{
fminn[i][0]=a[i];
}
for(int j=1;j<=log2(n);j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
fminn[i][j]=min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r)
{
if(l>r)
{
swap(l,r);
}
l++;
int t=log2(r-l+1);
return min(fminn[l][t],fminn[r-(1<<t)+1][t]);
}
}T;
int sa[100010],rk[200010],oldrk[200010],id[100010],cnt[100010],key[100010],height[100010];
int val(char x)
{
return (int)x;
}
void counting_sort(int n,int m)
{
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)
{
cnt[key[i]]++;
}
for(int i=1;i<=m;i++)
{
cnt[i]+=cnt[i-1];
}
for(int i=n;i>=1;i--)
{
sa[cnt[key[i]]]=id[i];
cnt[key[i]]--;
}
}
void init(char s[],int len)
{
int m=127,tot=0,num=0;
for(int i=1;i<=len;i++)
{
rk[i]=val(s[i]);
id[i]=i;
key[i]=rk[id[i]];
}
counting_sort(len,m);
for(int w=1;tot!=len;w<<=1,m=tot)
{
num=0;
for(int i=len;i>=len-w+1;i--)
{
num++;
id[num]=i;
}
for(int i=1;i<=len;i++)
{
if(sa[i]>w)
{
num++;
id[num]=sa[i]-w;
}
}
for(int i=1;i<=len;i++)
{
key[i]=rk[id[i]];
}
counting_sort(len,m);
for(int i=1;i<=len;i++)
{
oldrk[i]=rk[i];
}
tot=0;
for(int i=1;i<=len;i++)
{
tot+=(oldrk[sa[i]]!=oldrk[sa[i-1]]||oldrk[sa[i]+w]!=oldrk[sa[i-1]+w]);
rk[sa[i]]=tot;
}
}
for(int i=1,j=0;i<=len;i++)
{
j-=(j>=1);
while(s[i+j]==s[sa[rk[i]-1]+j])
{
j++;
}
height[rk[i]]=j;
}
T.init(len,height);
}
int lcp(int x,int y)
{
return T.query(rk[x],rk[y]);
}
}S;
int main()
{
int k,lens,lent,sum=0,i,j,h;
cin>>k>>(s+1)>>(t+1);
lens=strlen(s+1);
lent=strlen(t+1);
for(i=1;i<=lens;i++)
{
tmp[i]=s[i];
}
tmp[lens+1]='&';
for(i=1;i<=lent;i++)
{
tmp[lens+1+i]=t[i];
}
S.init(tmp,lens+1+lent);
for(h=1;h<=lent;h++)
{
memset(f,-0x3f,sizeof(f));
f[0][k]=0;
for(i=0;i<=k;i++)
{
for(j=-k;j<=k;j++)
{
if(f[i][j+k]>=0&&f[i][j+k]+j>=0&&f[i][j+k]+j+h-1<=lent)
{
if(f[i][j+k]+1<=lens&&f[i][j+k]+j+1+h-1+lens+1<=lens+1+lent)
{
f[i][j+k]+=S.lcp(f[i][j+k]+1,f[i][j+k]+j+1+h-1+lens+1);
}
if(j-1+k>=0)
{
f[i+1][j-1+k]=max(f[i+1][j-1+k],f[i][j+k]+(f[i][j+k]!=lens));
}
f[i+1][j+k]=max(f[i+1][j+k],f[i][j+k]+(f[i][j+k]!=lens));
f[i+1][j+1+k]=max(f[i+1][j+1+k],f[i][j+k]);
}
}
}
for(j=-k;j<=k;j++)
{
for(i=0;i<=k;i++)
{
if(f[i][j+k]==lens&&lens+j>0&&lens+j+h-1<=lent)
{
ans[i]++;
break;
}
}
}
}
for(i=0;i<=k;i++)
{
sum+=ans[i];
}
cout<<sum<<endl;
return 0;
}
后记
多倍经验：QOJ 5312.Levenshtein Distance
标签：int,题解,BJOI2015,fminn,lens,num,100010,隐身术,rk From： https://www.cnblogs.com/The-Shadow-Dragon/p/18534640