【bzoj3555】[Ctsc2014]企鵝QQ 簡單哈希

傳送門

題目分析

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

比如有如下字符串：$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;
}

?