字符串哈希

参考 https://blog.csdn.net/wxy2635618879/article/details/103968837

作为一个喜爱map的蒟蒻 我突然在CSP前意识到自己根本不会哈希。我对哈希的理解止步于自己yy出的求值。。。

子串哈希 O(1)

\(hash=hash_{r}-hash_{l-1}base^{r-l+1}\)

证明：
\(hash(1,r)=\sum_{i=1}^r \sum a_ibase^{r-i}\)
\(hash(1,l-1)=\sum_{i=1}^{l-1} \sum a_ibase^{l-1-i}\)

\(hash(l,r)=\sum_{i=l}^r \sum a_ibase^{r-i}\)
\(hash(l,r)=\sum_{i=1}^r \sum a_ibase^{r-i}-\sum_{i=1}^{l-1} \sum a_ibase^{r-i}\)
\(hash(l,r)=hash(1,r)-\sum_{i=1}^{l-1} \sum a_ibase^{l-1-i}base^{r-l+1}\)
\(hash(l,r)=hash(1,r)-hash(1,l-1)base^{r-l+1}\)

字符串哈希

原文：https://www.cnblogs.com/zdsrs060330/p/13934944.html