Sliding Window Hash Homework Solution using C++

To complete a c++ assignment, the goal is to master the technical details of updating a “sliding window hash” in an array.

First Task: Storing the Input in an Array of Integers

Second Task: Counting Symmetries the Slow Way Please write code that counts the total number of symmetries in the way we just described; that is, For every index, i = 1, 2, 3, ...Determine if the entire array starting at index 0matches the entire array starting at index i (wrapping around as appropriate). Stop at the first such index i that is a match. Output the array length divided by i.

Third Task: Counting Symmetries Faster with Hashing We can make our algorithm faster as follows: Let H be a polynomial hash of the entire array, starting at index 0For every index i = 1, 2, 3, ...Let H’ be the updated hash for the entire array, starting at index iIf H == H’, then check to see if there is actually a match at index i. Stop at the first such index i that is a match. Output the array length divided by i. The slow.cpp will contain the code for the non-hashing and the fast.cpp contains the hashing.

Solution:

#include < iostream> using namespace std; int compute_hash(const int n, const int start, const int x, const int p, const int* A) { int H = 0; for ( int i = 0; i < n; i++ ) { H = (int)( ( (long long)H * x + A[( start + i ) % n] ) % p ); } return H; } int main( int argc, char** argv ) { int *A; int *B; int i, j, k; char cmd; int value; int match; int H, H_dash; int seed = 13; int p = 1000000007; int tmp; // First Task: Storing the Input in an Array of Integers cin >> k; A = new int[ 2 * k ]; j = 0; for ( i = 0; i < k; i++ ) { cin >> cmd >> value; switch ( cmd ) { case 'F': A[j++] = 0; break; case 'L': A[j++] = 1; break; case 'R': A[j++] = 2; break; default: break; } A[j++] = value; } // Second Task: Counting Symmetries the Slow Way // For every index i = 1, 2, 3, ... for ( i = 1; i < k; i++ ) { match = 1; // Determine if the entire array starting at index 0 // matches the entire array starting at index i (wrapping around as appropriate). for ( j = 0; j < k; j++ ) { if ( ( A[( 2 * ( i + j ) ) % ( 2 * k )] != A[2 * j] ) || ( A[( 2 * ( i + j ) + 1 ) % ( 2 * k )] != A[2 * j + 1] ) ) { match = 0; break; } } // Stop at the first such index i that is a match. if ( match == 1 ) { break; } } // Output the array length divided by i cout << ( k / i ) << endl; return 0; } // Third Task: Counting Symmetries Faster with Hashing // Let H be a polynomial hash of the entire array, starting at index 0 H = compute_hash( 2 * k, 0, seed, p, A ); B = new int[2 * k]; B[0] = seed % p; for ( i = 1; i < 2 * k; i++ ) { // x^n % p = ( ( x^(n - 1) % p ) * ( x % p ) ) % p; B[i] = ( (long long)B[i - 1] * ( seed % p ) ) % p; } // For every index i = 1, 2, 3, ... tmp = A[0] % p; H_dash = ( (long long)( ( p + ( H % p ) - ( ( (long long)tmp * B[2 * k - 2] ) % p ) ) % p ) * ( seed % p ) ) % p + tmp; for ( i = 1; i < k; i++ ) { // Let H' be the updated hash for the entire array, starting at index i // H' = ((H - A[i] x^(n - 1)) x + A[i]) % p // => H' = ((H - A[i] x^(n - 1)) x) % p + A[i] % p // => H' = ( ((H - A[i] x^(n - 1)) % p) (x % p) ) % p + A[i] %p // => H' = ( ( p + H % p - ( ( A[i] % p ) ( x^(n - 1) % p ) % p ) ) % p ) * ( x % p ) % p + A[i] % p tmp = A[2 * i - 1] % p; H_dash = ( (long long)( ( p + ( H_dash % p ) - ( ( (long long)tmp * B[2 * k - 2] ) % p ) ) % p ) * ( seed % p ) ) % p + tmp; // If H == H', then check to see if there is actually a match at index i. if ( H == H_dash ) { match = 1; // Determine if the entire array starting at index 0 // matches the entire array starting at index i (wrapping around as appropriate). for ( j = 0; j < k; j++ ) { if ( ( A[( 2 * ( i + j ) ) % ( 2 * k )] != A[2 * j] ) || ( A[( 2 * ( i + j ) + 1 ) % ( 2 * k )] != A[2 * j + 1] ) ) { match = 0; break; } } // Stop at the first such index i that is a match. if ( match == 1 ) { break; } } tmp = A[2 * i] % p; H_dash = ( (long long)( ( p + ( H_dash % p ) - ( ( (long long)tmp * B[2 * k - 2] ) % p ) ) % p ) * ( seed % p ) ) % p + tmp; } // Output the array length divided by i cout << ( k / i ) << endl; return 0; }