題目鏈接：點擊查看

題目大意：給出一個m和l，還有一個字符串，問在s中所有長度為m*l的連續子字符串中，有多少個滿足條件的子字符串

這里的滿足條件指的是，長度為m*l的子字符串，可以分成m個長度為l的子字符串的子字符串，若這m個新的子字符串互不相同，則稱原子字符串滿足條件

互不相同的定義是指只要有一個位置的字母不同則稱兩個字符串互不相同

綜上所述，問在s中有多少個滿足條件的子字符串

題目分析：這個題目，一看n給的特別大，很容易想到先哈希一下，但光哈希是不夠的，我覺得后面的優化才是關鍵，在哈希完之后，我們該怎么判斷有多少種滿足條件的子字符串呢？我們只能枚舉首尾，然后判斷，這樣枚舉的時間復雜度，最壞的話大概就是字符串s的長度拉滿，也就是1e5，然后m*l等于1e5/2，這樣的時間復雜度就是1e5/2*1e5/2，也就達到了n*n的復雜度，肯定是不行的，想了半天無果后去網上搜題解開闊一下思路，發現大佬們可以直接將復雜度下降到n，具體操作就是我們不需要枚舉首尾，在外層只需要枚舉i，范圍0~l作為起點即可，然后每次在我們統計完i~i+m*l后，可以進行滑動窗口的操作，也就是讓整個m*l的子字符串在可操作范圍內每次都向右移動長度為l的單位，這樣的話是利用了尺取法的思想，將n*n的復雜度下降到了n，具體操作還可以借助map的自動去重功能輔助實現，也是比較方便的，具體的看代碼吧，注釋會說明的

代碼：

#include<iostream> #include<cstdlib> #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<sstream> #include<unordered_map> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;char s[N];ull _hash[N];ull f[N];unordered_map<ull,int>mp;void Hash()//打個哈希表 {_hash[0]=s[0]-'a';f[0]=1;int len=strlen(s);for(int i=1;i<len;i++){_hash[i]=_hash[i-1]*131+s[i]-'a';f[i]=f[i-1]*131;} }ull gethash(int l,int r)//O(1)獲得區間內的哈希值 {return _hash[r]-_hash[l-1]*f[r-l+1]; }int main() { // freopen("input.txt","r",stdin);int m,l;while(scanf("%d%d",&m,&l)!=EOF){scanf("%s",s);int n=strlen(s);Hash();int ans=0;for(int i=0;i<l&&i+m*l<=n;i++)//枚舉范圍是0~l{mp.clear();for(int j=i;j<i+m*l;j+=l)//將這個小區間的哈希值用map記錄一下mp[gethash(j,j+l-1)]++;if(mp.size()==m)//若有m個不同的哈希值，就代表有m個不同的區間，也就是m個互不相同的字符串ans++;//答案相應加一for(int j=i;j+m*l+l<=n;j+=l)//尺取{ull pos=gethash(j,j+l-1);//刪掉后面的區間mp[pos]--;if(mp[pos]==0)mp.erase(pos);mp[gethash(j+m*l,j+m*l+l-1)]++;//加上前面的區間if(mp.size()==m)ans++;}}printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 4821 String(字符串哈希+优化)的全部內容，希望文章能夠幫你解決所遇到的問題。

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