傳送門

題目分析

題意即求有多少對字符串只相差一個字符，枚舉刪除每個字符后的哈希， 看有多少相等即可。

比如有如下字符串：$Sd123$，其中S部分的哈希值為H，刪除的是d，則原字符串的哈希值為$$(((H * T + d) * T + 1) * T + 2) * T + 3 = H * T^4 + d * T^3 + 1 * T^2 + 2 * T + 3$$

刪除過后就為$$((H * T + 1) * T + 2) * T +3 = H * T^3 +?1 * T^2 + 2 * T + 3$$

也就是將1以前的哈希值全部剪去然后加上d之前的哈希值乘以$T^{len - delpos}$。

code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> using namespace std;const int N = 3e4 + 5, L = 205, Mod = 23333; typedef unsigned long long ull; const ull H = 149; ull hash[N][L], poww[L], go[N << 2], t[N]; int ecnt, adj[Mod + 5], nxt[N << 2]; int n, l, m, cnt; char s[N][L];inline ull del(int k, int d){return hash[k][l] - hash[k][d] * poww[l - d] + hash[k][d - 1] * poww[l - d]; }int main(){scanf("%d%d%d", &n, &l, &m);for(int i = 1; i <= n; i++)scanf("%s", s[i] + 1);for(int i = 1; i <= n; i++)for(int j = 1; j <= l; j++)hash[i][j] = hash[i][j - 1] * H + s[i][j];poww[0] = 1;for(int i = 1; i <= L; i++) poww[i] = poww[i - 1] * H;for(int j = 1; j <= l; j++){for(int i = 1; i <= n; i++)t[i] = del(i, j);sort(t + 1,t + n + 1);int sum = 1;for(int i = 2; i <= n; i++){if(t[i] == t[i - 1]){cnt += sum;sum++;}else sum = 1;}}printf("%d", cnt);return 0; }

?

轉載于:https://www.cnblogs.com/CzYoL/p/7434515.html

總結

以上是生活随笔為你收集整理的【bzoj3555】[Ctsc2014]企鹅QQ 简单哈希的全部內容，希望文章能夠幫你解決所遇到的問題。

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