bzoj 5073 [Lydsy1710月赛]小A的咒语

bzoj 5073 [Lydsy1710月赛]小A的咒语

​​ 题意：给定a,b两个串 求是否能将a拆成x个以内的串完全匹配 b

考虑设dp[i][j]表示当前在a中第i个位置用了j段在b中匹配的最大是多少

那么可以i知道朴素dp[i][j]=max(dp[i-1][j],dp[i][j])

然后可以考虑枚举后面匹配的长度 比如是z 那么分别就是dp[i+z][j+1]=max(dp[i][j]+z,dp[i+z][j+1])

但是发现其实贪心的选lcp即可 因为lcp相比拆开来看的话 因为我们求最长 那么一定不会差 并且还能用更少的段数完成我们所需要的东西 所以直接要匹配的话匹配lcp即可 那么用SA求出之后直接lcp即可

#include#include#includeusing namespace std;const int N=2e5+10;int rk[N<<1],rk1[N<<1],height[N],Log[N],T,n,m,x,k,mm,cnt[N],sa[N],dp[100010][110];char s[N],s1[N];int mn[N][20],tmp[N];inline int lcp(int x,int y){ x=rk[x];y=rk[y];if (x>y) swap(x,y);++x;int t=Log[y-x+1]; return min(mn[x][t],mn[y-(1<>1]+1; while(T--){ scanf("%d%d%d",&n,&m,&x);int nn=n+1; scanf("%s",s+1);s[++n]='#';scanf("%s",s1+1); for (int i=1;i<=m;++i) s[++n]=s1[i]; memset(rk,0,sizeof(rk));k=0;mm=30; for (int i=1;i<=300;++i) cnt[i]=0; for (int i=1;i<=n;++i) cnt[s[i]]=1; for (int i=1;i<=255;++i) cnt[i]+=cnt[i-1]; for (int i=1;i<=n;++i) rk[i]=cnt[s[i]]; for (int p=1;k!=n;p<<=1,mm=k){ for (int i=1;i<=mm;++i) cnt[i]=0; for (int i=1;i<=n;++i) ++cnt[rk[i+p]]; for (int i=1;i<=mm;++i) cnt[i]+=cnt[i-1]; for (int i=n;i;--i) tmp[cnt[rk[i+p]]--]=i; for (int i=1;i<=mm;++i) cnt[i]=0; for (int i=1;i<=n;++i) ++cnt[rk[i]]; for (int i=1;i<=mm;++i) cnt[i]+=cnt[i-1]; for (int i=n;i;--i) sa[cnt[rk[tmp[i]]]--]=tmp[i]; memcpy(rk1,rk,sizeof(rk)>>1);rk[sa[1]]=k=1; for (int i=2;i<=n;++i){ if (rk1[sa[i-1]]!=rk1[sa[i]]||rk1[sa[i-1]+p]!=rk1[sa[i]+p]) ++k; rk[sa[i]]=k; } }k=0;memset(dp,0,sizeof(dp)); for (int i=1;i<=n;++i){ if(rk[i]==1) continue; k=k==0?0:k-1; while(s[i+k]==s[sa[rk[i]-1]+k]) ++k; height[rk[i]]=k; }memset(mn,0,sizeof(mn)); for (int i=1;i<=n;++i) mn[i][0]=height[i]; /*for (int i=1;i<=n;++i) printf("%d ",height[i]);puts(""); for (int i=1;i<=n;++i){ for (int j=sa[i];j<=n;++j) putchar(s[j]);puts(""); }*/ for (int j=1;j<=Log[n];++j) for (int i=1;i+(1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。