SequenceHash.cpp

/*
 * Author : Nikhil Garg
 * Date   : 2011-12-29
 * A SequenceHash data structure.
 * Initial construction takes O(N) time. 
 * After that it can query hashcode of any contiguous subsequence in O(1)
 *
 */

struct SequenceHash
{
    vector<long long> prefixHash, powers;
    
    SequenceHash(const vector<int>& seq)
    {
        int L = seq.size();
        prefixHash.resize(L+1); powers.resize(L+1);
        prefixHash[0] = 0LL;    powers[0] = 1LL;
        
        for(int i = 1; i <= L;i++)
        {
            prefixHash[i] = prefixHash[i-1] * 31LL + seq[i-1];
            powers[i] = powers[i-1] * 31LL;
        }        
    }
    
    long long hash(int a, int b)           // Returns hash code for seq[a..b], both endpoints inclusive
    {
        return prefixHash[b+1] - prefixHash[a] * powers[b-a+1];
    }
};


int main()
{
   //Example usage
    int A[] = { 1, 2, 3, 1, 2, 3};
    SequenceHash sh(VI(A));             // Just instantiate the SequenceHash 
    assert( sh.hash(0,2) == sh.hash(3,5));
}