Back to Leetcode

Readme

String/2156.Find-Substring-With-Given-Hash-Value/Readme.md

latest455 B
Original Source

2156.Find-Substring-With-Given-Hash-Value

这是一道Rolling Hash的裸题,就是将一个字符串转化为26进制的整数。注意到Hash的高位在右边,所以我们需要从右往左进行滑窗滚定。

每个回合里,先砍掉原先的最高位乘以26^(k-1),然后整体乘上26,再加上新引入的最低位。

由于涉及到减法,可能会产生负数,所以每次取模时采用(x+M)%M的方式更为稳妥。