BOI Day2 necklace 题解

题意：

求A,B串连续子串首尾相连形成的项链中，最长的相同的项链长度及子串的初始位置。
项链旋转，翻转后相同就被视为相同。

分析:

首先，两条项链相同，那么它们在原串中有这样的形状：

只考虑旋转后相同的字符串，我们可以将其分成两段，分别处理。
对于每个位置对$（i,p）$,我们希望求出从$i$向左延伸到最远的$q$,从$p$向右延伸到最远的$j$,使得$A[q,i]=B[p,j]$,将$L$记为$g[i][p]$。
同理，我们还要求出从$i+1$向右延伸到最远的$x$,从$p-1$向左延伸到最远的$y$,使得$A[i+1,x]=B[y,p-1]$,将它的长度记为$f[i+1][p-1]$。
这样我们就得到了在$（i,p）$分成两段的相同项链的最大长度。
现在的问题变成怎么求$g[i][p]$和$f[i+1][p-1]$。
定义一个辅助的数组$dp[i][j]$表示从$i$向左延伸到最远的$q$，从$j$向左延伸到最远的$p$，使得$A[q,i]=B[p,j]$,将$L$记为$dp[i][j]$
如果$A[i]==A[j]$,则$dp[i][j]=dp[i-1][j-1]+1$;
否则$dp[i][j]=0$。
求出$dp[i][j]$后，用$dp$数组算出相应的左端点，更新$g$数组和$f$数组。
最后：
$g[i][j]=max(g[i][j],g[i][j-1]-1)$
$f[i][j]=max(f[i][j],f[i][j+1]-1)$

考虑翻转，将B串翻转过来再做一遍相同的操作即可。
代码：

#include
#include
#include
using namespace std;
#define MAXN 3005
int dp[MAXN][MAXN],g[MAXN][MAXN],f[MAXN][MAXN],ns,nt,ps,pt,ans;
char s[MAXN],t[MAXN];
void Work(bool flag)
{for(int i=max(ns,nt);i>=0;i--) dp[0][i]=dp[i][0]=0;for(int i=0;i<=ns;i++)for(int j=0;j<=nt;j++) g[i][j]=f[i][j]=0;for(int i=1;i<=ns;i++)for(int j=1;j<=nt;j++)if(s[i]==t[j]){dp[i][j]=dp[i-1][j-1]+1;g[i][j-dp[i][j]+1]=max(g[i][j-dp[i][j]+1],dp[i][j]);f[i-dp[i][j]+1][j]=max(f[i-dp[i][j]+1][j],dp[i][j]);}else dp[i][j]=0;for(int i=1;i<=ns;i++)for(int j=1;j<=nt;j++)g[i][j]=max(g[i][j],g[i][j-1]-1);for(int i=1;i<=ns;i++)for(int j=nt;j>=1;j--)f[i][j]=max(f[i][j],f[i][j+1]-1);for(int i=0;i<=ns;i++)for(int j=0;j<=nt;j++)if(g[i][j+1]+f[i+1][j]>ans){ans=g[i][j+1]+f[i+1][j];ps=i-g[i][j+1];pt=j-f[i+1][j];if(flag) pt=nt-pt-ans;}
}
int main()
{freopen("necklace.in","r",stdin);freopen("necklace.out","w",stdout);scanf("%s%s",s+1,t+1);ns=strlen(s+1),nt=strlen(t+1);Work(0);reverse(t+1,t+nt+1);Work(1);printf("%d\n%d %d\n",ans,ps,pt);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！