題目鏈接：點擊查看

題目大意：給出一串只由A,C,G,T組成的字符串，再給出一個數字k，問每個長度為k的連續子串，出現的次數最多是多少次

題目分析：O(n)哈希一下，O(n)更新一下用無序map維護的cnt容器，最后O(n)一遍cnt求出最大值即可

在這個題目有幾個點需要注意一下：

能在main函數中實現的都扔到main函數中去實現，不要包裝成函數然后反復調用，時間開銷不容小覷

范圍for循環比正常for循環要快，原理不明

如果沒有用cin加速外掛配合string類，還是老老實實用char字符串+scanf輸入吧

就這樣，一個毫無細節的字符串哈希，T了一早晨之后終于以800毫秒險過~

上代碼了：

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e6+100;unordered_map<ull,int>cnt;char str[N];int len;ull _hash[N],p[N];void Hash() {_hash[0]=0;for(int i=1;i<=len;i++)_hash[i]=_hash[i-1]*131+str[i]-'A';p[0]=1;for(int i=1;i<=len;i++)p[i]=p[i-1]*131; }int main() {scanf("%s",str+1);len=strlen(str+1);int k;scanf("%d",&k);Hash();for(int i=1;i+k-1<=len;i++){int l=i;int r=i+k-1;cnt[_hash[r]-_hash[l-1]*p[r-l+1]]++;}int ans=-1;for(auto it:cnt)//本來只是想偷懶，沒想到比正常的for快了將近200ms。。if(it.second>ans)ans=it.second;printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - DNA(字符串哈希)的全部內容，希望文章能夠幫你解決所遇到的問題。

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