【题解】 Codeforces Edu41 F. k-substrings （字符串Hash）

题面戳我

Solution

• 我们正着每次都要枚举从长到短，时间复杂度承受不了，但是我们可以发现一个规律，假设某次的答案为\(x\)，那么这个字符串为\(A+X+B\)组成，无论中间的\(X\)是重叠还是空余的，我们都可以发现，这个字符串可以改成\(a+A'+X+B'+b\)，所以下一次砍掉两边，这个\(A'\)中没有\(a\)与\(B'\)匹配，\(B'\)中同理没有\(b\)与\(A'\)匹配，所以公共串长度至少\(-2\)。
• 有了上面那个性质，我们再倒着来做，我们把砍掉两边改成在两边加上两个字符，那么这次答案，至多是上次答案\(+2\)，那么答案就只能从\(lastans+2,lastans,\cdots,1\)中查找，我们如果判断到一个答案符合前缀和后缀一样，我们就可把这个数作为答案，直接\(break\)即可，长度\(1\)的子串前缀和后缀都没有答案就是\(-1\)。
• 我们来验证下时间复杂度的正确性，因为我们每次都是从\(lastans+2\)，开始然后向后减，其实就与\(KMP\)一样（我不会），减的次数由加的次数决定，然后我们加的次数不会多于\(n/2+1\)，忽略常数，再加上\(Hash\)，所以我们就可以证明时间复杂度大概是\(O(n)\)的了
• 判断字符串相同用\(Hash\)

Code

//It is coded by ning_mew on 7.23 #include<bits/stdc++.h> #define LL long long using namespace std;const int maxn=1e6+7;int n; char ch[maxn]; LL MOD[3]={19260817,20000909,19491001}; LL Hash[3][maxn],Pow[3][maxn]; int ans[maxn];bool check(int s,int len){int mid,t;if(n%2){mid=(n+1)/2;t=2*mid-s;}else {mid=n/2;t=mid-s+mid+1;}for(int i=0;i<3;i++){int box1=((Hash[i][s+len-1]-Hash[i][s-1]*Pow[i][len])%MOD[i]+MOD[i])%MOD[i];int box2=((Hash[i][t]-Hash[i][t-len]*Pow[i][len])%MOD[i]+MOD[i])%MOD[i];if(box1!=box2)return false;}return true; } void work1(){ans[(n+1)/2]=-1;for(int i=(n+1)/2-1;i>=1;i--){//cout<<"----------------------"<<endl;ans[i]=-1;for(int k=ans[i+1]+2;k>=1;k-=2){//cout<<k<<endl;if(check(i,k)){ans[i]=k;break;}}}for(int i=1;i<=(n+1)/2;i++){printf("%d ",ans[i]);} printf("\n"); } void work2(){if(ch[n/2]==ch[n/2+1])ans[n/2]=1;else ans[n/2]=-1;for(int i=n/2-1;i>=1;i--){ans[i]=-1;for(int k=ans[i+1]+2;k>=1;k-=2){//cout<<k<<endl;if(check(i,k)){ans[i]=k;break;}}}for(int i=1;i<=n/2;i++){printf("%d ",ans[i]);} printf("\n"); } int main(){scanf("%d",&n);scanf("%s",ch+1);for(int j=0;j<3;j++){Pow[j][0]=1;for(int i=1;i<=n;i++){Hash[j][i]=(Hash[j][i-1]*27+ch[i]-'a')%MOD[j];Pow[j][i]=Pow[j][i-1]*27%MOD[j];}}if(n%2)work1();else work2();return 0; }

博主蒟蒻，随意转载。但必须附上原文链接：http://www.cnblogs.com/Ning-Mew/，否则你会场场比赛爆0！！！

转载于:https://www.cnblogs.com/Ning-Mew/p/9356955.html

总结

以上是生活随笔为你收集整理的【题解】 Codeforces Edu41 F. k-substrings （字符串Hash）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。