字符串哈希

一句话理解

字符串哈希把字符串变成整数（或一对整数）。

为什么要学

快速比较子串。

讲解

多项式哈希：h = h*P + s[i]，再对模数取模。子串哈希用前缀差。

例子

把 “abc” 看成 P 进制数。

常见错误

• 单模容易被卡，要用双哈希。
• P 和模选成 10 和 1e9 这种差选择。