java计算给定字符串所有前缀的哈希值的子字符串的哈希值
假设给您一个长度为N
的字符串S
,以及该字符串所有前缀的哈希值数组S
{
hash[0][i]
表示以索引i
结尾的字符串S
前缀的哈希M
表示一个大的素整数R
表示哈希函数中使用的基数
还将为您提供所使用的哈希函数:
for(int i = 0; i < N; i++) {
hash[0][i] = ( (i > 0 ? hash[0][i - 1] : 0) * R + S.charAt(i) ) % M;
}
我们需要根据需要计算hash[i][j]
。根据上述信息,我们能否找出O(1)
中S
子字符串的哈希值,即hash[i][j]
where, i,j > 0 and i,j < N
注意:数组hash[][]
最初只包含字符串S
前缀的预计算哈希值hash[0][0....N-1]
# 1 楼答案
子字符串s[A..B]的哈希为
使用模幂运算来计算R mod M的幂。不,除非你预先计算了R的幂,否则在O(1)中是不可能计算的