java - 给定字符串所有前缀的哈希值，计算子字符串的哈希值

Question

假设给你一个字符串 S长度N以及字符串所有前缀的哈希值数组 S hash[0][0...N-1] .

hash[0][i]表示字符串前缀的散列 S以索引 i 结尾. 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]在需要的基础上。我们能找出S的子串的哈希值吗？在 O(1)即 hash[i][j]鉴于上述信息？

where, i,j > 0 and i,j < N

注:数组hash[][]最初仅包含预先计算的哈希值 hash[0][0....N-1]字符串的前缀 S .

Answer 1

子串s[A..B]的哈希为

hash[B] - R^(B - A + 1) * hash[A - 1] mod M

使用模幂计算 R mod M 的幂。不，除非您预先计算 R 的幂，否则不可能在 O(1) 中计算它。