正題

---

題目大意

求長度為n個一個字符串長度為m不同的子串個數

---

解題思路

用字符串hash判斷字符串是否相同，然后時間復雜度$O(n^2)$，然后我們因為自然溢出所以不能開桶，那就開map。然后就會愉快的被卡，所以再加一個自定義模數。

---

code

#pragma GCC optimize(2) #include<cstdio> #include<algorithm> #include<map> #define ull long long #define p 13331 #define p2 131 #define YMW 1000007 #define N 200010 using namespace std; int n,m,ans; ull pow[N],h[N],h2[N],pow2[N]; char s[N]; map<pair<ull,ull>,bool> ok; ull ask(int l,int r)//循環區間 {return (h[r]-h[l-1]*pow[r-l+1]%YMW+YMW)%YMW; } ull ask2(int l,int r)//循環區間 {return (h2[r]-h2[l-1]*pow2[r-l+1]%YMW+YMW)%YMW; } int main() {scanf("%d%d",&n,&m);scanf("%s",s+1);pow[0]=pow2[0]=1;for(int i=1;i<=n;i++){pow[i]=(pow[i-1]*p)%YMW;pow2[i]=(pow2[i-1]*p2)%YMW;h[i]=(h[i-1]*p%YMW+s[i]-'a'+1)%YMW;//hash值1h2[i]=(h2[i-1]*p2%YMW+s[i]-'a'+1)%YMW;//hash值2}for(int i=m;i<=n;i++){ull k,k2;if(!ok[make_pair(k=ask(i-m+1,i),k2=ask2(i-m+1,i))]){ok[make_pair(k,k2)]=true;//標記ans++;//猩的子串}}printf("%d",ans); }

總結

以上是生活随笔為你收集整理的nssl1211-好文章【字符串hash,map】的全部內容，希望文章能夠幫你解決所遇到的問題。

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