題面戳我

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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。