假设您获得了长度为 N 的字符串 S 以及字符串 S hash[0][0...N-1] 的所有前缀的哈希值数组 .
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）中计算它 .