哈希

[Ir1d]

https://oi-wiki.org/string/hash/

[Drew233]

啊哈

[FighterNan]

Practice this problem.

[CyaceQuious]

那个，最后的例题代码中求子串哈希的部分是假的吧，只不过碰巧在比较相邻且长度相等的子串时不会出错所以能AC。
正确的写法应该是 h(S[l,r]) = h_r - h_{l-1} * K^{r-l+1} ?

[ce-amtic]

@CyaceQuious
那个，最后的例题代码中求子串哈希的部分是假的吧，只不过碰巧在比较相邻且长度相等的子串时不会出错所以能AC。
正确的写法应该是 h(S[l,r]) = h_r - h_{l-1} * K^{r-l+1} ?

+1，建议尽早更正一下

[1292224662]

第一部分对f(s)的定义和下面讲述的内容以及示例代码不符

事实上，字符串（假设一个长为3的字符串abc）哈希可以是a(p^2)+bp+c也可以是a+bp+c(p^2)，这两种哈希方式都可以，但它们在计算一个子串哈希值时用的式子是不一样的，所以初学时应特别注意二者使用上的区别，别用混了

而这里第一部分定义的f(s)是上述后者的形式，而下面的示例代码和字串哈希计算式则实际上是使用了上述前者的f(s)定义。这会给初学者带来挺大的误导的......而且子串哈希的那个式子直接凭空出现也会使初学者比较困惑，建议解释一下

这里推一篇CF的blog吧，个人认为讲的比较清楚：https://codeforces.com/blog/entry/60445

[NachtgeistW]

第一部分对f(s)的定义和下面讲述的内容以及示例代码不符

事实上，字符串（假设一个长为3的字符串abc）哈希可以是a(p^2)+bp+c也可以是a+bp+c(p^2)，这两种哈希方式都可以，但它们在计算一个子串哈希值时用的式子是不一样的，所以初学时应特别注意二者使用上的区别，别用混了

而这里第一部分定义的f(s)是上述后者的形式，而下面的示例代码和字串哈希计算式则实际上是使用了上述前者的f(s)定义。这会给初学者带来挺大的误导的......而且子串哈希的那个式子直接凭空出现也会使初学者比较困惑，建议解释一下

这里推一篇CF的blog吧，个人认为讲的比较清楚：https://codeforces.com/blog/entry/60445

Hello～可以开一个Pull Request帮忙改进一下吗？

[1292224662]

@NachtgeistW

第一部分对f(s)的定义和下面讲述的内容以及示例代码不符

事实上，字符串（假设一个长为3的字符串abc）哈希可以是a(p^2)+bp+c也可以是a+bp+c(p^2)，这两种哈希方式都可以，但它们在计算一个子串哈希值时用的式子是不一样的，所以初学时应特别注意二者使用上的区别，别用混了

而这里第一部分定义的f(s)是上述后者的形式，而下面的示例代码和字串哈希计算式则实际上是使用了上述前者的f(s)定义。这会给初学者带来挺大的误导的......而且子串哈希的那个式子直接凭空出现也会使初学者比较困惑，建议解释一下

这里推一篇CF的blog吧，个人认为讲的比较清楚：https://codeforces.com/blog/entry/60445

Hello～可以开一个Pull Request帮忙改进一下吗？

开了，不太会用github，希望没出锅（捂脸

[jpy-cpp]

为什么说那个是效率低下的版本？

[xiaohaowudi]

“允许k次失配的字符串匹配” 那个小节是不是有笔误？不是“当且仅当s'和s长度相等”， 应该是"当且仅当s'和p长度相等"