bzoj沒有題面，題面在vijos。

---

所以說讀入char再丟給string并不會慢…

短串扔到hash表里。
長串的前半部分復制一份，然后在上面跑，若長串的后半部分出現過，則答案加上后面的hash值的出現次數。

寫了雙hash+掛鏈表，因為寫了指針，并且雙hash常數大，所以TLE+MLE，還有莫名其妙的WA…………

自然溢出+map在vijos上就是過不了……T兩個點，不過在bzoj還是能A的。

看題解有人寫的在bool數組中若已被占用則往后跳…在bzoj實測表現和map差不多…vijos也是T兩個點…

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<map> using namespace std;typedef unsigned long long ULL; typedef long long LL; const int SZ = 4000010; const int base = 13331;string S1[SZ],S2[SZ];map<ULL,int> h;ULL hash[SZ],mi[SZ];ULL gethash(string s) {ULL ans = 0;for(int i = 0;i < s.length();i ++)ans = ans * base + s[i] - 'a' + 1;return ans; }ULL getstr(int l,int r) {int len = r - l + 1;return hash[r] - hash[l - 1] * mi[len]; }char s[SZ];void read(char s[]) {memset(s,0,sizeof(s));int tot = 0;char a = getchar();for(;a < 'a' || a > 'z';a = getchar());for(;a >= 'a' && a <= 'z';a = getchar())s[tot ++] = a; }int main() {int n,m,len1,len2;scanf("%d%d%d%d",&n,&m,&len1,&len2);mi[0] = 1;for(int i = 1;i <= len1 + len2;i ++)mi[i] = mi[i - 1] * base;for(int i = 1;i <= n;i ++)read(s),S1[i] = s;for(int i = 1;i <= m;i ++)read(s),S2[i] = s;if(len1 < len2) swap(S1,S2),swap(n,m),swap(len1,len2);for(int i = 1;i <= m;i ++)h[gethash(S2[i])] ++;int len = (len1 + len2) >> 1;LL ans = 0;for(int i = 1;i <= n;i ++){for(int j = 0;j < len * 2;j ++)hash[j + 1] = hash[j] * base + S1[i][j % len] - 'a' + 1;ULL x = 0;for(int j = len;j < len1;j ++)x = x * base + S1[i][j] - 'a' + 1;for(int j = 1;j <= len;j ++){ULL y = getstr(j,j + len1 - len - 1);if(x == y){ULL a = getstr(j + len1 - len,j + len - 1);ans += h[a];}}}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的【bzoj4084】[Sdoi2015]bigyration hash的全部內容，希望文章能夠幫你解決所遇到的問題。

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