【字符串】字符串哈希

因为习惯了STL，所以一直没有接触这块儿的内容，今天cf碰到学着用了一下发现还蛮好用的

单哈希

字符串哈希 简单来说就是把一个字符串对应到一个数上，且一个字符串唯一对应一个数，一个数也唯一对应一个字符串

怎么进行这个操作呢？

我们定义一个 base 和一个 mod

字符串 $s_1{s}_2{s}_3$ 就可以表示为 $(s_1{-}^{\prime }{a}^{\prime })\times bas{e}^2+(s_2{-}^{\prime }{a}^{\prime })\times bas{e}^1+(s_3{-}^{\prime }{a}^{\prime })\times bas{e}^0$ （未取模的结果）

base 一般取值 131 1331 13331 （以此类推）

mod 建议取一些奇奇怪怪的值，比如说 1e13+39

通过这个操作把字符串转换成数，之后判断两个字符串是否相等，只需要判断两个数是否相等就可以了

双哈希

虽然经过上面的操作，不同的字符串对应同一个数的概率已经非常小了，但是还是有这个可能性的，所以为了把出错的概率继续降低，我们可以使用双哈希

定义 mod1 mod2 ，让每个字符串对应两个数，只有当两个字符串产生的两个数完全一致时，才判定这两个字符串相等。（依此类推，还可以进行更多次数的哈希降低出错概率）

板子

预处理base的次方

p[0] = 1;
for (int i = 1; i < N; i ++ ) p[i] = p[i - 1] * base % mod1;

将字符串转换成数

int hash_cal(string s)
{int res = 0;for (int i = 0; i < s.size(); i ++ )res = (res * base % mod1 + s[i] - 'a') % mod1;return res;
}

查询

for (int i = 0; i < n; i ++ )
{string s;cin >> s;hash_set[i] = hash_cal(s);
}
sort(hash_set, hash_set + n);
for (int i = 0; i < m; i ++ )
{string s;cin >> s;int tmp = hash_cal(s);if (*lower_bound(hash_set, hash_set + n, tmp) == tmp) cout << "YES\n";else cout << "NO\n";
}