Codeforces961F. k-substrings

$n \leq 1000000$的字符串，对每一个子串$i$~$n-i+1$，求他最长的一个既是前缀又是后缀的子串。

这题要求的东西具有“对称性”，不充分利用难以解决。这里的“对称性”不仅指询问是对称的，更指要求的那个公共部分是对称的——不对称的相同的子串对答案没有丝毫贡献。

从贡献的角度入手，就是求每个前缀$i$和后缀$n-i+1$的一个在前缀$i$的末尾的、在后缀$n-i+1$的开头的一个最长公共串。嗯那赶紧二分+哈希。额等等，从$i$向前延伸，从$n-i+1$向后延伸，字符串是否相同，这样一个函数不单调哦。但是，如果您从前缀$i$的中点处和后缀$n-i+1$的中点处向两边分别延伸，这样字符串是否相同就是一个单调函数了。

因此转移战线，枚举对称相同串的中间位置$i$，然后$i$和$n-i+1$分别向两边延伸看最长的相同串多长，用二分+哈希判断。假设这次二分的答案是$2x-1$，那么$ans_{i-x+1}$就会$max$上$2x-1$。但这个串对$i-x+1$到$i$处的答案都是有贡献的，并且贡献每次减2，为了体现这一点只需要最后统计答案时$ans_i \ \ =max(ans_i,ans_{i-1}-2)$即可。

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 //#include<queue>

 //#include<vector>

 #include<algorithm>

 //#include<iostream>

 //#include<assert.h>

 using namespace std;

 int n;

 #define maxn 2000011

 char s[maxn];

 int h1[maxn],h2[maxn],p1[maxn],p2[maxn],mod1=,mod2=;

 int geth1(int L,int R) {return (h1[R]-h1[L-]*1ll*p1[R-L+]%mod1+mod1)%mod1;}

 int geth2(int L,int R) {return (h2[R]-h2[L-]*1ll*p2[R-L+]%mod2+mod2)%mod2;}

 int ans[maxn];

 int main()

 {

     scanf("%d%s",&n,s+);

     h1[]=h2[]=;

     for (int i=;i<=n;i++) h1[i]=(h1[i-]*27ll+s[i]-'a'+)%mod1,h2[i]=(h2[i-]*27ll+s[i]-'a'+)%mod2;

     p1[]=p2[]=;

     for (int i=;i<=n;i++) p1[i]=p1[i-]*27ll%mod1,p2[i]=p2[i-]*27ll%mod2;

     for (int i=;i<=(n+)>>;i++) ans[i]=-;

     for (int i=;i<=n>>;i++)

     {

         int L=,R=i,p=n-i+;

         while (L<R)

         {

             int mid=(L+R+)>>,a=i-mid+,b=i+mid-,c=p-mid+,d=p+mid-;

             if (geth1(a,b)==geth1(c,d) && geth2(a,b)==geth2(c,d)) L=mid;

             else R=mid-;

         }

         ans[i-L+]=max(ans[i-L+],*L-);

     }

     for (int i=;i<=(n+)>>;i++)

     {

         ans[i]=max(ans[i],ans[i-]-);

         printf("%d ",ans[i]);

     }

     return ;

 }

巴特西

Codeforces961F. k-substrings

最新文章

热门文章