I have a big problem in task: find any hash of substring in O(1) time

Hash of input string with length=n is calculate by formula:

h(S) = ( s(1)*a^(n-1) s(2)*a^(n-2) ... s(n-1)a s(n) )%R , where 's' is ASCII code.

1)I Find all prefix hash in string

2)I tryid to get hash of substring by formula:

h(R-L) = (h(R) - h(L-1))*a^(R-L 1) For example string = 'abcdefgh', substing is 'd' . a = 1000 , R = 1000009;

My code in java:

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 ;
    }
}

In function getHash I tryed to get hash of substring 'd' . Right answer is 100 , but I get 999857. Help me, where is error?

CodePudding user response：

result is

(hashes[end] - hashes[start-1] * z % m   m) % m

but no

(hashes[end] - hashes[start-1]   m) % m * z % m