From 60f43a3f1c1ff2f87ab64ef5e17654742c264cf7 Mon Sep 17 00:00:00 2001 From: ouuan Date: Wed, 11 Sep 2019 08:49:26 +0800 Subject: [PATCH] :pencil2: fix typo --- docs/string/hash.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/string/hash.md b/docs/string/hash.md index 96e7e82d..1c28a51a 100644 --- a/docs/string/hash.md +++ b/docs/string/hash.md @@ -68,7 +68,7 @@ void cmp(const string& s, const string& t) { 一般采取的方法是对整个字符串先预处理出每个前缀的哈希值,将哈希值看成一个 $b$ 进制的数对 $M$ 取模的结果,这样的话每次就能快速求出子串的哈希了: -令 $f_i(s)$ 表示 $f(s[1..i])$ ,那么 $f(s[l..r])=\frac{f_r[s]-f_{l-1}(s)}{b^{l-1}}$ ,其中 $\frac{1}{b^{l-1}}$ 也可以预处理出来,用 [乘法逆元](../math/inverse.md) 或者是在比较哈希值时等式两边同时乘上 $b$ 的若干次方化为整式均可。 +令 $f_i(s)$ 表示 $f(s[1..i])$ ,那么 $f(s[l..r])=\frac{f_r(s)-f_{l-1}(s)}{b^{l-1}}$ ,其中 $\frac{1}{b^{l-1}}$ 也可以预处理出来,用 [乘法逆元](../math/inverse.md) 或者是在比较哈希值时等式两边同时乘上 $b$ 的若干次方化为整式均可。 这样的话,就可以在 $O(\text{串长})$ 的预处理后每次 $O(1)$ 地计算子串的哈希值了。 -- 2.11.0