有两种方式，个人习惯用 $h(n) = \sum_{i=1}^{n} s_i \times base^i$。常用 $base = 139,MOD = 1011451423$。
有 $h(l,r) = (h(r) - h(l-1)) \times base^{n-r}$。
对于反串，有 $h(n) = \sum_{i=1}^{n} s_i \times base^{n-i+1},h(l,r) = (h(r) - h(l)) \times base^{l-1}$。
可以用树状数组或线段树动态维护。
有两种方式，个人习惯用 $h(n) = \sum_{i=1}^{n} s_i \times base^i$。常用 $base = 139,MOD = 1011451423$。
有 $h(l,r) = (h(r) - h(l-1)) \times base^{n-r}$。
对于反串，有 $h(n) = \sum_{i=1}^{n} s_i \times base^{n-i+1},h(l,r) = (h(r) - h(l)) \times base^{l-1}$。
可以用树状数组或线段树动态维护。