前缀哈希计算子串哈希出错求助：O(1)时间子串哈希问题

问题描述 #

实现「O(1)时间内获取任意子串哈希值」时出现结果错误，哈希公式定义为：

h(S) = ( s(1)*a^(n-1) + s(2)*a^(n-2)+...+s(n-1)a+s(n) )%R，其中s为字符的ASCII码，n为字符串长度。

实现步骤：

• 计算字符串所有前缀哈希值
• 尝试用公式计算子串哈希：h(R-L) = (h(R) - h(L-1))*a^(R-L+1)

测试场景：字符串为abcdefgh，子串为d，a=1000，R=1000009。正确结果应为100（'d'的ASCII码），但实际运行代码得到999857。

原代码：

import java.io.IOException;
import java.math.BigInteger;

public class PrefixHashFAILED {

    public static long[] hashes;

    public static void main(String[] args) throws IOException {

        int a = 1000;
        int modul = 1000009;
        char[] data = "abcdefgh".toCharArray();
        hashes = new long[data.length];

        long res = 0L;
        for( int i = 0 ; i < data.length ; i ++){
            res = ((res*a)%modul +  data[i]%modul)%modul;
            hashes[i] = res;
        }
         System.out.println(getHash(3,3,a,modul));
   }

    private static long getHash(int start, int end , int a, int  m) {
        long x = (hashes[end] - hashes[start-1]+m)%m;
        long z = BigInteger.valueOf(a).pow(end - start + 1  ).mod(BigInteger.valueOf(m)).intValue();
        return (x*z)%m ;
    }
}

错误分析 #

1. 子串哈希公式逻辑完全错误
   假设前缀哈希h[k]表示前k个字符的哈希（即h[k] = s(1)*a^(k-1)+s(2)*a^(k-2)+...+s(k)），子串s[L..R]的哈希推导应为：
   h[R] = s(1)*a^(R-1)+...+s(L-1)*a^(R-L+1) + s(L)*a^(R-L)+...+s(R)
   而h[L-1]*a^(R-L+1) = s(1)*a^(R-1)+...+s(L-1)*a^(R-L+1)
   因此子串哈希正确公式是(h[R] - h[L-1]*a^(R-L+1))%R，你写的公式把乘法位置完全搞反，导致结果偏离。

2. 前缀哈希下标与索引混淆
   原代码中hashes[i]对应前i+1个字符的哈希（0-based数组），但getHash(3,3)传入的start=3对应0-based的第3个字符（即'd'），此时start-1=2，hashes[2]是前3个字符的哈希，这部分下标逻辑本身没问题，但公式错误放大了问题。

3. 幂次计算效率低且存在精度风险
   每次调用getHash用BigInteger计算幂次，不仅效率低，intValue()还可能因溢出丢失精度，正确做法是预处理幂次数组。

修正方案 #

修正后的代码如下：

import java.io.IOException;

public class PrefixHashFixed {

    public static long[] hashes;
    public static long[] powA; // 预处理a的幂次数组

    public static void main(String[] args) throws IOException {

        int a = 1000;
        int modul = 1000009;
        char[] data = "abcdefgh".toCharArray();
        int n = data.length;
        hashes = new long[n + 1]; // 1-based数组，hashes[0] = 0，hashes[k]对应前k个字符的哈希
        powA = new long[n + 1];
        powA[0] = 1;

        // 预处理前缀哈希和幂次
        for (int i = 0; i < n; i++) {
            hashes[i + 1] = ((hashes[i] * a) % modul + data[i] % modul) % modul;
            powA[i + 1] = (powA[i] * a) % modul;
        }

        // 子串'd'对应1-based的第4个字符，传入start=4, end=4
        System.out.println(getHash(4, 4, modul));
    }

    private static long getHash(int start, int end, int m) {
        // 应用正确的子串哈希公式
        long temp = (hashes[start - 1] * powA[end - start + 1]) % m;
        // 加m避免负数结果
        return (hashes[end] - temp + m) % m;
    }
}

修正要点 #

• 将前缀哈希改为1-based数组，hashes[0]=0，hashes[k]对应前k个字符的哈希，贴合公式定义，减少下标混淆。
• 预处理powA数组存储a^k % modul的值，避免重复计算，提升效率。
• 修正子串哈希计算公式，使用(h[end] - h[start-1] * powA[end-start+1]) % m，并通过加m确保结果非负。
• 测试时传入1-based索引（'d'是第4个字符），运行结果为100，符合预期。

内容的提问来源于stack exchange，提问作者Gosha Efimenko