题解 P5479 【[BJOI2015]隐身术】

bellmanford

2020-02-03 12:27:24

Solution

先$\%$一下神仙的$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); } ```