引言
当我们对于一组值域较大但数据总数较少的数据无法处理时，其中一个处理方法就是对其进行离散化，把大值映射到小值内。但是，如果这组数据是由字符串组成的，我们又该如何对其处理？字符串Hash就是一种将字符串进行“离散化”，将字符串映射到一个可以接受的数值内，方便对数据进行处理。
做法
假设我们现在要将一个字符串(S)通过字符串(Hash)映射到一个值内。
我们可以将(S)看作一个(P)进制数，对(S)中的每个字符赋予一个权值。
假设(S)是由小写字符组成的，那么对于每一个字符，我们可以将(a)到(z)赋值为(1)到(26)。
举个例子，当(P)取(26)，(S)取(aab)时，它的Hash值就是(1*26^2+1*26^1+2*26^0)，并对这个值适当取模。
对于一个字符串(dsakhdkas)来说，它的Hash值为((4 19 1 11 8 4 11 1 19)_{26})，则
(Hash_0=0)
(Hash_1=4)
(Hash_2=4*26+19)
(Hash_3=4*26^2+19*26+1)
(Hash_4=4*26^3+19*26^2+1*26^1+11)
(Hash_n=...)
如果要取(S_{2-4})(sak)，则它的(Hash)值为((4 19 1 11)_{26}-(4 0 0 0)_{26}=(0 19 1 11)_{26})，即(Hash_4-Hash_1*26^3)
故对于一个字符串(S)，(S_{l-r})的(Hash)值为(Hash_r-Hash_{l-1}*P^{r-l+1})
为了减少(Hash)的冲突，建议取一个质数作为(P)，通常情况下取(131)或(13331)。而且在方便且准确的情况下，我们可以直接将(Hash)数组和(P)的若干次方开为(unsigned long long)或(unsigned int)，使之自然溢出。
例题
兔子与兔子
模板题，直接上代码：
// 代码中f即为Hash数组，P为131的若干次方
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define mp make_pair
#define il inline
#define ri register int
#define rep(i, a, b) for (ri i = a; i <= b; ++ i)
#define per(i, a, b) for (ri i = a; i >= b; -- i)
const int N = 1000009;
int len, n;
ll p[N], f[N];
char s[N];
il char gc() {
static char ibuf[1048576], *iS, *iT;
return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, 1048576, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++);
}
void readstr() {
register char c = gc();
while (c >= 'a' && c <= 'z') s[++ len] = c, c = gc();
}
void pre() {
p[0] = 1;
rep (i, 1, len) {
p[i] = p[i - 1] * 131;
f[i] = f[i - 1] * 131 + s[i] - 'a' + 1;
}
}
template<class I>
il void read(I &x) {
register char c = gc(); x = 0; ri f = 0;
while(!isdigit(c)) f = (c == '-') ? 1 : f, c = gc();
while(isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = gc();
x = f ? -x : x;
}
int main() {
readstr();
pre();
read(n);
while (n --) {
int l1, r1, l2, r2;
read(l1), read(r1), read(l2), read(r2);
if (f[r1] - f[l1 - 1] * p[r1 - l1 + 1] == f[r2] - f[l2 - 1] * p[r2 - l2 + 1]) puts("Yes");
else puts("No");
}
return 0;
}
再上一道模板题
珍珠项链
给出一个字符串(S)，将其平均分成若干段，询问每段长度为多少时有最多不同的字符串数(每一段可以反转)
这题只要正反各做一遍(Hash)，暴力枚举长度即可。时间复杂度(O(nln_n))
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define rep(i, a, b) for (ri i = a; i <= b; ++i)
#define per(i, a, b) for (ri i = a; i >= b; --i)
const int N = 200009;
typedef unsigned long long ll;
int n, a[N], res, vis[N], cnt;
ll p[N], f1[N], f2[N];
vector<int> vec, output;
vector<ll> h[1000009];
il char gc() {
static char ibuf[1048576], *iS, *iT;
return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, 1048576, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
}
template <class I>
il void read(I &x) {
register char c = gc();
x = 0;
ri f = 0;
while (!isdigit(c)) f = (c == '-') ? 1 : f, c = gc();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = gc();
x = f ? -x : x;
}
il ll hasha(int l, int r) { return f1[r] - f1[l - 1] * p[r - l + 1]; }
il ll hashb(int l, int r) { return f2[l] - f2[r + 1] * p[r - l + 1]; }
il int Hash(ll x) { return x % 999997 + 1; }
int check(int x1, ll y1, int x2, ll y2) {
rep(i, 0, (int)h[x1].size() - 1) if (h[x1][i] == y1) return 0;
rep(i, 0, (int)h[x2].size() - 1) if (h[x2][i] == y2) return 0;
return 1;
}
int main() {
read(n);
p[0] = 1;
rep(i, 1, n) {
read(a[i]);
p[i] = 19260817 * p[i - 1];
f1[i] = f1[i - 1] * 19260817 + a[i];
}
per(i, n, 1) f2[i] = f2[i + 1] * 19260817 + a[i];
rep(len, 1, n) {
int ans = 0;
cnt = 0;
for (ri l = 1; l + len - 1 <= n; l += len) {
int r = l + len - 1;
ll u = hasha(l, r), v = hashb(l, r);
int x = Hash(u), y = Hash(v);
if (check(x, u, y, v)) {
++ans;
h[x].push_back(u);
vis[++cnt] = x;
if (u != v) {
h[y].push_back(v);
vis[++cnt] = y;
}
}
}
if (ans > res) {
output.clear();
res = ans;
output.push_back(len);
} else if (ans == res)
output.push_back(len);
rep(i, 1, cnt) while (h[vis[i]].size()) h[vis[i]].pop_back();
}
printf("%d %d
", res, output.size());
rep(i, 0, (int)output.size() - 1) printf("%d ", output[i]);
puts("");
return 0;
}