题解 P5479 【[BJOI2015]隐身术】
bellmanford
2020-02-03 12:27:24
先$\%$一下神仙的$dp$做法
------------
这题一看$n+m≤10^5$,就知道要合并起来了(大雾
再看$k≤5$,那就只用直接$DFS$枚举操作方案
记录在字符串A的匹配位置x和在字符串B的匹配位置y
还要记录剩余操作数判断是否终止
每次跳掉两个后缀的lcp(也就是最长前缀)
目前跳到的地方一定是不相同的字符
也就是$A[x] \ne B[y]$
必然进行一次操作
插入:在$A[x]$前面插入一个和$B[y]$一样的字符,$x$的位置不变,$y$往后一个
删除:将$A[x]$删去,$x$向后一个
修改:将$A[x]$的字符改为$B[y]$的字符,$x,y$均往后一个
每次某个串匹配到结尾时,$B$中的某个区间的前缀都会合法,注意到这些合法的前缀长度与$A$长度相差一定不超过$k$,于是用一个$2*k+1$的差分数组记录答案即可
每次$DFS$由于转移时一定会增加一次操作数,所以最多递归$k$次,最差复杂度为$O(3^k)$
所以总复杂度为$O(n\log n+n3^k)$
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define int long long
const int M=1e5+5;
int n,m=125,ans=0,k,sl,tl,L,R,now,pre[M];
int tx[M],tp[M],sa[M],rk[M],height[M];
int st[M][35],log[M];
char r[M],s[M],t[M];
void jsort(){
for(int i=0;i<=m;i++) tx[i]=0;
for(int i=1;i<=n;i++) tx[rk[i]]++;
for(int i=1;i<=m;i++) tx[i]+=tx[i-1];
for(int i=n;i>=1;i--) sa[tx[rk[tp[i]]]--]=tp[i];
}
void Build_SA(){//板子
jsort();//O(n)的基排
for(int w=1,p=0;p<n;m=p,w<<=1){
p=0;
for(int i=1;i<=w;i++) tp[++p]=n-w+i;
for(int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
jsort();
std::swap(tp,rk);
rk[sa[1]]=p=1;
for(int i=2;i<=n;i++){
if(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w]) rk[sa[i]]=p;
else rk[sa[i]]=++p;
}
}
for(int i=1;i<=n;i++) sa[i-1]=sa[i]-1;//将SA给变为0-(n-1)
}
void Build_Height(){//求height
for(int i=0;i<n;i++) rk[sa[i]]=i;
int k=0;
for(int i=0;i<n;i++){
if(!rk[i]) continue;
if(k) k--;
int j=sa[rk[i]-1];
while(r[i+k]==r[j+k]) k++;
height[rk[i]]=k;
}
}
void Build_ST(){//st表优化求lcp
for(int i=2;i<=n;i++) log[i]=log[i>>1]+1;
for(int i=0;i<n;i++) st[i][0]=height[i];
for(int j=1;j<=25;++j){
for(int i=0;i+(1<<j)-1<n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
}
int Query(int l,int r){//O(1)查询两个字符串分别的后缀l和后缀r的lcp的长度
int k=log[r-l+1];
return min(st[l][k],st[r-(1<<k)+1][k]);
}
void DFS(int x,int y,int z){//爆搜,x代表在字符串A的匹配位置,y代表在字符串B的匹配位置,z代表剩余操作数
if(z>k) return ;
int l=rk[x],r=rk[y];
if(l>r) swap(l,r);
int lcp=Query(l+1,r);
x+=lcp,y+=lcp;//跳过相同的字符串
if(x==sl||y==n){
int d=k-z-(sl-x);
if(d<0) return ;
int l=max(y-1-d,now),r=min(y-1+d,n-1);
L=min(l,L),R=max(r+1,R);
pre[l]++,pre[r+1]--;
return ;
}
DFS(x+1,y,z+1),DFS(x,y+1,z+1),DFS(x+1,y+1,z+1);//三种状态转移
}
signed main(){
scanf("%lld%s%s",&k,s,t);
sl=strlen(s),tl=strlen(t);
for(int i=0;i<sl;i++) r[n++]=s[i];r[n++]='#';//分开前后字符串
for(int i=0;i<tl;i++) r[n++]=t[i];
for(int i=1;i<=n;i++) rk[i]=r[i-1],tp[i]=i;
Build_SA(),Build_Height(),Build_ST();
for(int i=0;i<tl;i++){
now=sl+i+1,L=n-1,R=0;
DFS(0,sl+i+1,0);
for(int j=L;j<=R;++j) ans+=(pre[j]+=pre[j-1])>0;
for(int j=L;j<=R;++j) pre[j]=0;
}
printf("%lld\n",ans);
}
```