Finding Hash of Substring [i, j] in O(1) using O(|S|) pre computation

general
, , , , ,
1

Given a string S of length n characters, is it possible to calculate the Hash of its substring [i, j] (From index i to index j. Inclusive) in O(1) using some form of precomputation ? Maybe a modification of the Rolling Hash ?

Similar Problem

Problem Statement TACHEMIS

I have seen it being used in a similar problem where in a string was given in a compressed form. Meaning, e.g. if the string is "aaabccdeeee" then the compressed form is:

3 a
1 b
2 c
1 d
4 e

How data was stored

They are stored in an str[] array as :

str[] = [{'a','3'}, {'b','1'}, {'c','2'}....]

HASHING Concept that was used in the solutions

And programmers had used the following hash concept to find if the given substring is a Palindrome or not. Given a substring of string S as (i,j), they computed the hash of substring [i , (i+j)/2] and the reverse hash of substring [(i+j+2)/2, j] and checked if they were equal or not. So if they wanted to check if in string S = "daabac" whether substring [1, 5] is a a palindrome or not, they computed the following :

h1 = forward_hash("aa") 
h2 = reverse_hash("ba")
h1 == h2

Code for the Hashing Concept

The hash precomputation was done as follows :

/* Computing the Prefix Hash Table */
pre_hash[0] = 0;
for(int i=1;i<=len(str);i++)
{
    pre_hash[i] = pre_hash[i-1]*very_large_prime + str[i].first;
    pre_hash[i] = pre_hash[i]  *very_large_prime + str[i].second;
}

/* Computing the Suffix Hash Table */
suff_hash[0] = 0;
for(int i=1;i<=len(str);i++)
{
    suff_hash[i] = suff_hash[i-1]*very_large_prime + str[K-i+1].first;
    suff_hash[i] = suff_hash[i]  *very_large_prime + str[K-i+1].second;
}

And then the hash was computed using the following functions :

/* Calculates the Forward hash of substring [i,j] */
unsigned long long CalculateHash(int i, int j)
{
    if(i>j)
        return -1;
    unsigned long long ret = pre_hash[j] - POW(very_large_prime, [2*(j-i+1)])*pre_hash[i-1];
    return ret;
}
/* Calculates the reverse hash of substring [i,j] */
unsigned long long CalculateHash_Reverse(int i, int j)
{
    unsigned long long ret = suff_hash[j] - POW(very_large_prime,[2*(j-i+1)])*suff_hash[i-1];
    return ret;
}

What I am trying to do

I am looking for a general approach to the above concept. Given a Pattern P, I want to check if the pattern P is present in a string S. I know the index (i) to check where it may be present. And I also know the length of pattern P represented as |P|. In short I want to check if hash of S[i, i+|P|] and hash of P match or not in O(1) using some form of pre computation on S.

Ignoring the time taken to compute hash of P else it would be O(1+|P|)

2

This is precisely the technique employed by Rabin-Karp string matching algorithm. You can start off with the Wikipedia article on Rabin-Karp. Or consult CLRS; it has a detailed explanation.

1 Like